mixed-integer programming

On the relative strength of families of intersection cuts arising from pairs of tableau constraints in mixed integer programs

  • Yogesh Awate
  • Gérard Cornuéjols
  • Bertrand Guenin
  • Levent Tunçel
    • Categories (Mixed) Integer Linear Programming Tags , ,

    We compare the relative strength of valid inequalities for the integer hull of the feasible region of mixed integer linear programs with two equality constraints, two unrestricted integer variables and any number of nonnegative continuous variables. In particular, we prove that the closure of Type~2 triangle (resp. Type~3 triangle; quadrilateral) inequalities, are all within a … Read more

    On the Augmented Lagrangian Dual for Integer Programming

  • Natashia Boland
  • Andrew C. Eberhard
    • Categories (Mixed) Integer Linear Programming Tags , ,

    We consider the augmented Lagrangian dual for integer programming, and provide a primal characterization of the resulting bound. As a corollary, we obtain proof that the augmented Lagrangian is a strong dual for integer programming. We are able to show that the penalty parameter applied to the augmented Lagrangian term may be placed at a … Read more

    Branch-and-Cut for Complementarity-Constrained Optimization

  • Ismael de Farias
  • Ernee Kozyreff
  • Ming Zhao
    • Categories Integer Programming Tags , , , , , ,

    We report and analyze the results of our computational testing of branch-and-cut for the complementarity-constrained optimization problem (CCOP). Besides the MIP cuts commonly present in commercial optimization software, we used inequalities that explore complementarity constraints. To do so, we generalized two families of cuts proposed earlier by de Farias, Johnson, and Nemhauser that had never … Read more

    Efficient Heuristic Algorithms for Maximum Utility Product Pricing Problems

  • Tor G.J. Myklebust
  • M. A. Sharpe
  • Levent Tunçel
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Combinatorial Optimization Tags , , ,

    We propose improvements to some of the best heuristic algorithms for optimal product pricing problem originally designed by Dobson and Kalish in the late 1980’s and in the early 1990’s. Our improvements are based on a detailed study of a fundamental decoupling structure of the underlying mixed integer programming (MIP) problem and on incorporating more … Read more

    On parallelizing dual decomposition in stochastic integer programming

  • Miles Lubin
  • Kipp Martin
  • Burhaneddin Sandikçi
  • Cosmin G. Petra
    • Categories Nonsmooth Optimization, Parallel Algorithms, Stochastic Programming Tags , , , , ,

    For stochastic mixed-integer programs, we revisit the dual decomposition algorithm of Car\o{}e and Schultz from a computational perspective with the aim of its parallelization. We address an important bottleneck of parallel execution by identifying a formulation that permits the parallel solution of the \textit{master} program by using structure-exploiting interior-point solvers. Our results demonstrate the potential … Read more

    Semi-continuous network flow problems

  • Shabbir Ahmed
  • Gustavo Angulo
  • Santanu S. Dey
    • Categories (Mixed) Integer Linear Programming, Network Optimization Tags , ,

    We consider semi-continuous network flow problems, that is, a class of network flow problems where some of the variables are restricted to be semi-continuous. We introduce the semi-continuous inflow set with variable upper bounds as a relaxation of general semi-continuous network flow problems. Two particular cases of this set are considered, for which we present … Read more

    On t-branch split cuts for mixed-integer programs

  • Sanjeeb Dash
  • Oktay Gunluk
    • Categories (Mixed) Integer Linear Programming Tags , , ,

    In this paper we study the t-branch split cuts introduced by Li and Richard (2008). They presented a family of mixed-integer programs with n integer variables and a single continuous variable and conjectured that the convex hull of integer solutions for any n has unbounded rank with respect to (n-1)-branch split cuts. It was shown … Read more

    The Triangle Closure is a Polyhedron

  • Amitabh Basu
  • Robert Hildebrand
  • Matthias Köppe
    • Categories Cutting Plane Approaches Tags , ,

    Recently, cutting planes derived from maximal lattice-free convex sets have been studied intensively by the integer programming community. An important question in this research area has been to decide whether the closures associated with certain families of lattice-free sets are polyhedra. For a long time, the only result known was the celebrated theorem of Cook, … Read more

    Mixed n-Step MIR Inequalities: Facets for the n-Mixing Set

  • Kiavash Kianfar
  • Sujeevraja Sanjeevi
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches Tags , , , , , ,

    Gunluk and Pochet [O. Gunluk, Y. Pochet: Mixing mixed integer inequalities. Mathematical Programming 90(2001) 429-457] proposed a procedure to mix mixed integer rounding (MIR) inequalities. The mixed MIR inequalities define the convex hull of the mixing set $\{(y^1,\ldots,y^m,v) \in Z^m \times R_+:\alpha_1 y^i + v \geq \b_i,i=1,\ldots,m\}$ and can also be used to generate valid … Read more

    Lattice-free sets, multi-branch split disjunctions, and mixed-integer programming

  • Sanjeeb Dash
  • Oktay Gunluk
  • Neil Dobbs
  • Tomasz Nowicki
  • Grzegorz Swirszcz
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches, Integer Programming Tags , ,

    In this paper we study the relationship between valid inequalities for mixed-integer sets, lattice-free sets associated with these inequalities and the multi-branch split cuts introduced by Li and Richard (2008). By analyzing $n$-dimensional lattice-free sets, we prove that for every integer $n$ there exists a positive integer $t$ such that every facet-defining inequality of the … Read more