Branch-and-Bound

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