Branch-and-Bound

An Enhanced Spatial Branch-and-Bound Method in Global Optimization with Nonconvex Constraints

  • Peter Kirst
  • Oliver Stein
  • Paul Steuermann
    • Categories Global Optimization Tags , , ,

    We discuss some difficulties in determining valid upper bounds in spatial branch-and-bound methods for global minimization in the presence of nonconvex constraints. In fact, two examples illustrate that standard techniques for the construction of upper bounds may fail in this setting. Instead, we propose to perturb infeasible iterates along Mangasarian-Fromovitz directions to feasible points whose … Read more

    A branch-and-bound algorithm for biobjective mixed-integer programs

  • Pietro Belotti
  • Banu Soylu
  • Margaret Wiecek
    • Categories (Mixed) Integer Linear Programming, Multi-Criteria Optimization Tags , , ,

    We propose a branch-and-bound (BB) algorithm for biobjective mixed-integer linear programs (BOMILPs). Our approach makes no assumption on the type of problem and we prove that it returns all Pareto points of a BOMILP. We discuss two techniques upon which the BB is based: fathoming rules to eliminate those subproblems that are guaranteed not to … Read more

    Branch-and-Sandwich: A Deterministic Global Optimization Algorithm for Optimistic Bilevel Programming Problems

  • Claire S. Adjiman
  • Polyxeni-Margarita Kleniati
    • Categories Global Optimization Theory Tags , ,

    We present a global optimization algorithm, Branch-and-Sandwich, for optimistic bilevel programming problems which satisfy a regularity condition in the inner problem. The functions involved are assumed to be nonconvex and twice continuously differentiable. The proposed approach can be interpreted as the exploration of two solution spaces (corresponding to the inner and the outer problems) using … Read more

    A Reliable Affine Relaxation Method for Global Optimization

  • Pierre Hansen
  • Frédéric Messine
  • Jordan Ninin
    • Categories Constrained Nonlinear Optimization, Global Optimization Theory Tags , , , ,

    An automatic method for constructing linear relaxations of constrained global optimization problems is proposed. Such a construction is based on affine and interval arithmetics and uses operator overloading. These linear programs have exactly the same numbers of variables and of inequality constraints as the given problems. Each equality constraint is replaced by two inequalities. This … Read more

    Covering Linear Programming with Violations

  • Shabbir Ahmed
  • Santanu S. Dey
  • Feng Qiu
  • Laurence A. Wolsey
    • Categories (Mixed) Integer Linear Programming Tags , ,

    We consider a class of linear programs involving a set of covering constraints of which at most k are allowed to be violated. We show that this covering linear program with violation is strongly NP-hard. In order to improve the performance of mixed-integer programming (MIP) based schemes for these problems, we introduce and analyze a … Read more

    What Could a Million Cores Do To Solve Integer Programs?

  • Thorsten Koch
  • Ted K. Ralphs
  • Yuji Shinano
    • Categories Integer Programming, Parallel Algorithms Tags , ,

    Given the steady increase in cores per CPU, it is only a matter of time until supercomputers will have a million or more cores. In this article, we investigate the opportunities and challenges that will arise when trying to utilize this vast computing power to solve a single integer linear optimization problem. We also raise … Read more

    Solving Mixed-Integer Nonlinear Programs by QP-Diving

  • Christian Kirches
  • Sven Leyffer
  • Ashutosh Mahajan
    • Categories (Mixed) Integer Nonlinear Programming, Quadratic Programming Tags , ,

    We present a new tree-search algorithm for solving mixed-integer nonlinear programs (MINLPs). Rather than relying on computationally expensive nonlinear solves at every node of the branch-and-bound tree, our algorithm solves a quadratic approximation at every node. We show that the resulting algorithm retains global convergence properties for convex MINLPs, and we present numerical results on … Read more

    Interdiction Branching

  • Andrea Lodi
  • Ted K. Ralphs
  • Fabrizio Rossi
  • Stefano Smriglio
    • Categories 0-1 Programming, Branch and Cut Algorithms Tags , , , , , ,

    This paper introduces interdiction branching, a new branching method for binary integer programs that is designed to overcome the difficulties encountered in solving problems for which branching on variables is inherently weak. Unlike traditional methods, selection of the disjunction in interdiction branching takes into account the best feasible solution found so far. In particular, the … Read more

    The Reliable Hub-and-spoke Design Problem: Models and Algorithms

  • Yu An
  • Bo Zeng
  • Yu Zhang
    • Categories Applications - OR and Management Sciences, Facility Planning and Design, Network Optimization Tags , ,

    This paper presents a study on reliable single and multiple allocation hub-and-spoke network design problems where disruptions at hubs and the resulting hub unavailability can be mitigated by backup hubs and alternative routes. It builds nonlinear mixed integer programming models and presents linearized formulas. To solve those difficult problems, Lagrangian relaxation and Branch-and-Bound methods are … Read more

    On Minimizing the Energy Consumption of an Electrical Vehicle

  • Mohamed Aidene
  • Abdelkader Merakeb
  • Frédéric Messine
    • Categories Applications - Science and Engineering, Branch and Cut Algorithms, Control Applications Tags , , , , ,

    The electrical vehicle energy management can be expressed as a Bang-Bang optimal control problem. In this work, we discuss on a new formulation and about the way to approximate this optimal control problem of Bang-Bang type via a discretization technique associated with a Branch-and-Bound algorithm. The problem that we focus on, is the minimization of … Read more