Integer Programming

The Sample Average Approximation Method Applied to Stochastic Routing Problems: A Computational Study

  • Shabbir Ahmed
  • Anton J. Kleywegt
  • George L. Nemhauser
  • Alexander Shapiro
  • Bram Verweij
    • Categories Cutting Plane Approaches, Stochastic Programming, Transportation Tags , , ,

    The sample average approximation (SAA) method is an approach for solving stochastic optimization problems by using Monte Carlo simulation. In this technique the expected objective function of the stochastic problem is approximated by a sample average estimate derived from a random sample. The resulting sample average approximating problem is then solved by deterministic optimization techniques. … Read more

    Polynomial interior point cutting plane methods

  • John E. Mitchell
    • Categories Cutting Plane Approaches, Linear Programming, Nonsmooth Optimization Tags , , ,

    Polynomial cutting plane methods based on the logarithmic barrier function and on the volumetric center are surveyed. These algorithms construct a linear programming relaxation of the feasible region, find an appropriate approximate center of the region, and call a separation oracle at this approximate center to determine whether additional constraints should be added to the … Read more

    Facets of The Cardinality Constrained Circuit Polytope

  • Petra Bauer
  • Jeff Linderoth
  • Martin Savelsbergh
    • Categories Integer Programming, Polyhedra

    The Cardinality Constrained Circuit Problem (CCCP) is the problem of finding a minimum cost circuit in a graph where the circuit is constrained to have at most $k$ edges. The CCCP is NP-Hard. We present classes of facet-inducing inequalities for the convex hull of feasible circuits. Article Download View Facets of The Cardinality Constrained Circuit … Read more

    A comparison of the Sherali-Adams, Lov\’asz-Schrijver and Lasserre relaxations for sh-1$ programming

  • Monique Laurent
    • Categories Combinatorial Optimization, Integer Programming, Linear, Cone and Semidefinite Programming Tags , , , ,

    Sherali and Adams \cite{SA90}, Lov\’asz and Schrijver \cite{LS91} and, recently, Lasserre \cite{Las01b} have proposed lift and project methods for constructing hierarchies of successive linear or semidefinite relaxations of a $0-1$ polytope $P\subseteq \oR^n$ converging to $P$ in $n$ steps. Lasserre’s approach uses results about representations of positive polynomials as sums of squares and the dual … Read more

    Augmented self-concordant barriers and nonlinear optimization problems with finite complexity.

  • Yurii Nesterov
  • Jean-Philippe Vial
    • Categories Integer Programming Tags , ,

    In this paper we study special barrier functions for the convex cones, which are the sum of a self-concordant barrier for the cone and a positive-semidefinite quadratic form. We show that the central path of these augmented barrier functions can be traced with linear speed. We also study the complexity of finding the analytic center … Read more

    Solving large MINLPs on computational grids

  • Jean-Pierre Goux
  • Sven Leyffer
    • Categories (Mixed) Integer Nonlinear Programming, Applications - Science and Engineering, Parallel Algorithms Tags , , ,

    We consider the solution of Mixed Integer Nonlinear Programming (MINLP) problems by a parallel implementation of nonlinear branch-and-bound on a computational grid or meta-computer. Computational experience on a set of large MINLPs is reported which indicates that this approach is efficient for the solution of large MINLPs. Citation Numerical Analysis Report NA/200, Department of Mathematics, … Read more

    The Integration of an Interior-Point Cutting-Plane Method within a Branch-and-Price Algorithm

  • Samir Elhedhli
  • Jean-Louis Goffin
    • Categories Applications - OR and Management Sciences, Integer Programming Tags , , , ,

    This paper presents a novel integration of interior point cutting plane methods within branch-and-price algorithms. Unlike the classical method, columns are generated at a “central” dual solution by applying the analytic centre cutting plane method (ACCPM) on the dual of the full master problem. First, we introduce improvements to ACCPM. We propose a new procedure … Read more

    Pattern search algorithms for mixed variable programming

  • Charles Audet
  • John E. Dennis, Jr.
    • Categories (Mixed) Integer Nonlinear Programming, Bound-constrained Optimization Tags , , , ,

    Many engineering optimization problems involve a special kind of discrete variable that {\em can} be represented by a number, but this representation has no significance. Such variables arise when a decision involves some situation like a choice from an unordered list of categories. This has two implications: The standard approach of solving problems with continuous … Read more

    Mixed variable optimization of the number and composition of heat intercepts in a thermal insulation system

  • Charles Audet
  • John E. Dennis, Jr.
  • Michael Kokkolaras
    • Categories (Mixed) Integer Nonlinear Programming, Bound-constrained Optimization, Mechanical Engineering Tags , , , , ,

    In the literature, thermal insulation systems with a fixed number of heat intercepts have been optimized with respect to intercept locations and temperatures. The number of intercepts and the types of insulators that surround them were chosen by parametric studies. This was because the optimization methods used could not treat such categorical variables. Discrete optimization … Read more