Branch-and-Bound

A Simplicial Branch-and-Bound Algorithm for Solving Quadratically Constrained Quadratic Programs

  • Jeff Linderoth
    • Categories Global Optimization Theory Tags , , ,

    We propose a branch-and-bound algorithm for solving nonconvex quadratically-constrained quadratic programs. The algorithm is novel in that branching is done by partitioning the feasible region into the Cartesian product of two-dimensional triangles and rectangles. Explicit formulae for the convex and concave envelopes of bilinear functions over triangles and rectangles are derived and shown to be … Read more

    A Grid-Enabled Distributed Branch-and-Bound Algorithm with

  • Clicia Castro
  • Lucia Drummond
  • Eduardo Uchoa
  • José Viterbo
    • Categories Parallel Algorithms Tags , ,

    This work introduces a distributed branch-and-bound algorithm to be run on computational Grids. Grids are often organized in a hierarchical fashion: clusters of processors connected via high-speed links, while the clusters themselves are geographically distant and connected through slower links. Our algorithm does not employ the usual master-worker paradigm and it considers the hierarchical structure … Read more

    Decomposition and Dynamic Cut Generation in Integer Linear Programming

  • M.V. Galati
  • Ted K. Ralphs
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Cutting Plane Approaches Tags , , , ,

    Decomposition algorithms such as Lagrangian relaxation and Dantzig-Wolfe decomposition are well-known methods that can be used to generate bounds for mixed-integer linear programming problems. Traditionally, these methods have been viewed as distinct from polyhedral methods, in which bounds are obtained by dynamically generating valid inequalities to strengthen the linear programming relaxation. Recently, a number of … Read more

    The Sample Average Approximation Method for Stochastic Programs with Integer Recourse

  • Shabbir Ahmed
  • Alexander Shapiro
    • Categories Integer Programming, Stochastic Approaches, Stochastic Programming Tags , , ,

    This paper develops a solution strategy for two-stage stochastic programs with integer recourse. The proposed methodology relies on approximating the underlying stochastic program via sampling, and solving the approximate problem via a specialized optimization algorithm. We show that the proposed scheme will produce an optimal solution to the true problem with probability approaching one exponentially … Read more

    The Maximum Box Problem and its Application to Data Analysis

  • Jonathan Eckstein
  • Peter L. Hammer
  • Ying Liu
  • Mikhail S. Nediak
  • Bruno Simeone
    • Categories Combinatorial Optimization, Data-Mining Tags , ,

    Given two finite sets of points $X^+$ and $X^-$ in $\R^n$, the maximum box problem consists in finding an interval (“box”) $B=\{x : l \leq x \leq u\}$ such that $B\cap X^-=\emptyset$, and the cardinality of $B\cap X^+$ is maximized. A simple generalization can be obtained by instead maximizing a weighted sum of the elements … Read more

    The Steinberg Wiring Problem

  • Kurt M. Anstreicher
  • Nathan Brixius
    • Categories 0-1 Programming, Production and Logistics Tags ,

    In 1961 Leon Steinberg formulated a “backboard wiring” problem that has resisted solution for 40 years. Steinberg’s wiring problem is to determine the locations of 34 computer components on a 4 by 9 grid so as to minimize the total length of the wiring required to interconnect them. The problem is an example of a … Read more

    A New Second-Order Cone Programming Relaxation for MAX-CUT problems

  • Masakazu Muramatsu
  • Tsunehiro Suzuki
    • Categories Combinatorial Optimization, Global Optimization Applications, Linear, Cone and Semidefinite Programming Tags , , , ,

    We propose a new relaxation scheme for the MAX-CUT problem using second-order cone programming. We construct relaxation problems to reflect the structure of the original graph. Numerical experiments show that our relaxation approaches give better bounds than those based on the spectral decomposition proposed by Kim and Kojima, and that the efficiency of the branch-and-bound … Read more

    A Multi-stage Stochastic Integer Programming Approach for Capacity Expansion under Uncertainty

  • Shabbir Ahmed
  • Alan J. King
  • Gyana Parija
    • Categories Integer Programming, Production and Logistics, Stochastic Programming Tags , , , ,

    This paper addresses a multi-period investment model for capacity expansion in an uncertain environment. Using a scenario tree approach to model the evolution of uncertain demand and cost parameters, and fixed-charge cost functions to model the economies of scale in expansion costs, we develop a multi-stage stochastic integer programming formulation for the problem. A reformulation … Read more

    Integrating SQP and branch-and-bound for Mixed Integer Nonlinear Programming

  • Sven Leyffer
    • Categories (Mixed) Integer Nonlinear Programming, Integer Programming Tags , ,

    This paper considers the solution of Mixed Integer Nonlinear Programming (MINLP) problems. Classical methods for the solution of MINLP problems decompose the problem by separating the nonlinear part from the integer part. This approach is largely due to the existence of packaged software for solving Nonlinear Programming (NLP) and Mixed Integer Linear Programming problems. In … Read more