(Mixed) Integer Linear Programming

A several new mixed integer linear programming formulations for exploration of online social networks

  • Zoran Gajic
    • Categories (Mixed) Integer Linear Programming, Facility Planning and Design, Optimization Software Benchmark Tags , ,

    The goal of this paper is to identify the most promising sets of closest assignment constraints from the literature, in order to improve mixed integer linear programming formulations for exploration of information flow within a social network. The direct comparison between proposed formulations is performed on standard single source capacitated facility location problem instances. Therefore, … Read more

    How important are branching decisions: fooling MIP solvers

  • Pierre Le Bodic
  • George L. Nemhauser
    • Categories (Mixed) Integer Linear Programming Tags , , , ,

    We show the importance of selecting good branching variables by exhibiting a family of instances for which an optimal solution is both trivial to find and provably optimal by a fixed-size branch-and-bound tree, but for which state-of-the-art Mixed Integer Programming solvers need an increasing amount of resources. The instances encode the edge-coloring problem on a … Read more

    A Note on Linear On/Off Constraints

  • Pierre Bonami
  • Hassan L. Hijazi
  • Adam Ouorou
    • Categories (Mixed) Integer Linear Programming, Polyhedra Tags ,

    This note studies compact representations of linear on/off constraints in mixed-integer linear optimization. A characterization of the convex hull of linear disjunctions is given in the space of original variables. This result can improve formulations of mixed-integer linear programs featuring on/off constraints by reducing the integrality gap in a Branch and Bound approach. Citation@article{, year={2014}, … Read more

    Robust optimal sizing of an hybrid energy stand-alone system

  • Alain Billionnet
  • Marie-Christine Costa
  • Pierre-Louis Poirion
    • Categories (Mixed) Integer Linear Programming Tags , ,

    This paper deals with the optimal design of a stand-alone hybrid system composed of wind turbines, solar photovoltaic panels and batteries. To compensate for a possible lack of energy from these sources, an auxiliary fuel generator uarantees to meet the demand in every case but its use induces important costs. We have chosen a two-stage … Read more

    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

    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

    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

    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

    The continuous knapsack set

  • Sanjeeb Dash
  • Oktay Gunluk
  • Laurence A. Wolsey
    • Categories (Mixed) Integer Linear Programming Tags ,

    We study the convex hull of the continuous knapsack set which consists of a single inequality constraint with n non-negative integer and m non-negative bounded continuous variables. When n = 1, this set is a slight generalization of the single arc flow set studied by Magnanti, Mirchandani, and Vachani (1993). We first show that in … Read more