Integer Programming

Equivariant Perturbation in Gomory and Johnson’s Infinite Group Problem. III. Foundations for the k-Dimensional Case with Applications to k=2

  • Amitabh Basu
  • Robert Hildebrand
  • Matthias Köppe
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches Tags , ,

    We develop foundational tools for classifying the extreme valid functions for the k-dimensional infinite group problem. In particular, (1) we present the general regular solution to Cauchy’s additive functional equation on bounded convex domains. This provides a k-dimensional generalization of the so-called interval lemma, allowing us to deduce affine properties of the function from certain … Read more

    CBLIB 2014: A benchmark library for conic mixed-integer and continuous optimization

  • Henrik A. Friberg
    • Categories Integer Programming, Linear, Cone and Semidefinite Programming, Optimization Software Benchmark Tags , , , , ,

    The Conic Benchmark Library (CBLIB 2014) is a collection of more than a hundred conic optimization instances under a free and open license policy. It is the first extensive benchmark library for the advancing field of conic mixed-integer and continuous optimization, which is already supported by all major commercial solvers and spans a wide range … Read more

    Derivative-free Methods for Mixed-Integer Constrained Optimization Problems

  • Giampaolo Liuzzi
  • Stefano Lucidi
  • Francesco Rinaldi
    • Categories (Mixed) Integer Nonlinear Programming, Applications - OR and Management Sciences, Constrained Nonlinear Optimization

    Methods which do not use any derivative information are becoming popular among researchers, since they allow to solve many real-world engineering problems. Such problems are frequently characterized by the presence of discrete variables which can further complicate the optimization process. In this paper, we propose derivative-free algorithms for solving continuously differentiable Mixed Integer NonLinear Programming … Read more

    Semidefinite Programming Reformulation of Completely Positive Programs: Range Estimation and Best-Worst Choice Modeling

  • Karthik Natarajan
  • Chung-Piaw Teo
    • Categories (Mixed) Integer Linear Programming, Semi-definite Programming

    We show that the worst case moment bound on the expected optimal value of a mixed integer linear program with a random objective c is closely related to the complexity of characterizing the convex hull of the points CH{(1 x) (1 x)’: x \in X} where X is the feasible region. In fact, we can … Read more

    Decomposition Algorithms for Two-Stage Chance-Constrained Programs

  • Simge Küçükyavuz
  • James R. Luedtke
  • Xiao Liu
    • Categories Branch and Cut Algorithms, Integer Programming, Stochastic Programming Tags , , ,

    We study a class of chance-constrained two-stage stochastic optimization problems where second-stage feasible recourse decisions incur additional cost. In addition, we propose a new model, where “recovery” decisions are made for the infeasible scenarios to obtain feasible solutions to a relaxed second-stage problem. We develop decomposition algorithms with specialized optimality and feasibility cuts to solve … Read more

    Strengthened Benders Cuts for Stochastic Integer Programs with Continuous Recourse

  • Merve Bodur
  • Sanjeeb Dash
  • Oktay Gunluk
  • James R. Luedtke
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches, Stochastic Programming Tags , ,

    With stochastic integer programming as the motivating application, we investigate techniques to use integrality constraints to obtain improved cuts within a Benders decomposition algorithm. We compare the effect of using cuts in two ways: (i) cut-and-project, where integrality constraints are used to derive cuts in the extended variable space, and Benders cuts are then used … Read more

    Deriving the convex hull of a polynomial partitioning set through lifting and projection

  • Trang T. Nguyen
  • Jean-Philippe P. Richard
  • Mohit Tawarmalani
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Theory Tags , ,

    Relaxations of the bilinear term, $x_1x_2=x_3$, play a central role in constructing relaxations of factorable functions. This is because they can be used directly to relax products of functions with known relaxations. In this paper, we provide a compact, closed-form description of the convex hull of this and other more general bivariate monomial terms (which … Read more

    Generating subtour constraints for the TSP from pure integer solutions

  • Ulrich Pferschy
  • Rostislav Stanek
    • Categories Combinatorial Optimization, Integer Programming Tags , ,

    The traveling salesman problem (TSP) is one of the most prominent combinatorial optimization problems. Given a complete graph G = (V, E) and nonnegative real edge distances d, the TSP asks for a shortest tour through all vertices with respect to the distances d. The method of choice for solving the TSP to optimality is … Read more

    A Trust Region Method for the Solution of the Surrogate Dual in Integer Programming

  • Natashia Boland
  • Andrew C. Eberhard
  • Angelos Tsoukalas
    • Categories (Mixed) Integer Linear Programming, Combinatorial Optimization, Nonsmooth Optimization Tags , ,

    We propose an algorithm for solving the surrogate dual of a mixed integer program. The algorithm uses a trust region method based on a piecewise affine model of the dual surrogate value function. A new and much more flexible way of updating bounds on the surrogate dual’s value is proposed, which numerical experiments prove to … Read more

    Polyhedral Approximation of Ellipsoidal Uncertainty Sets via Extended Formulations – a computational case study –

  • Andreas Bärmann
  • Andreas Heidt
  • Sebastian Pokutta
  • Alexander Martin
  • Christoph Thurner
    • Categories (Mixed) Integer Linear Programming, Robust Optimization, Second-Order Cone Programming Tags , , ,

    Robust optimization is an important technique to immunize optimization problems against data uncertainty. In the case of a linear program and an ellipsoidal uncertainty set, the robust counterpart turns into a second-order cone program. In this work, we investigate the efficiency of linearizing the second-order cone constraints of the latter. This is done using the … Read more