Integer 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

    Two-Term Disjunctions on the Second-Order Cone

  • Fatma Kılınç-Karzan
  • Sercan Yildiz
    • Categories (Mixed) Integer Nonlinear Programming, Second-Order Cone Programming Tags , , ,

    Balas introduced disjunctive cuts in the 1970s for mixed-integer linear programs. Several recent papers have attempted to extend this work to mixed-integer conic programs. In this paper we study the structure of the convex hull of a two-term disjunction applied to the second-order cone, and develop a methodology to derive closed-form expressions for convex inequalities … Read more

    Improving the integer L-shaped method

  • Shabbir Ahmed
  • Gustavo Angulo
  • Santanu S. Dey
    • Categories Integer Programming, Stochastic Programming Tags , , ,

    We consider the integer L-shaped method for two-stage stochastic integer programs. To improve the performance of the algorithm, we present and combine two strategies. First, to avoid time-consuming exact evaluations of the second-stage cost function, we propose a simple modification that alternates between linear and mixed-integer subproblems. Then, to better approximate the shape of the … 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

    Unifying semidefinite and set-copositive relaxations of binary problems and randomization techniques

  • Florian Jarre
  • Felix Lieder
  • Fatameh Bani Asadi Rad
    • Categories 0-1 Programming, Combinatorial Optimization Tags , , , , , ,

    A reformulation of quadratically constrained binary programs as duals of set-copositive linear optimization problems is derived using either \(\{0,1\}\)-formulations or \(\{-1,1\}\)-formulations. The latter representation allows an extension of the randomization technique by Goemans and Williamson. An application to the max-clique problem shows that the max-clique problem is equivalent to a linear program over the max-cut … 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{, … Read more

    Chance Constrained Mixed Integer Program: Bilinear and Linear Formulations, and Benders Decomposition

  • Yu An
  • Bo Zeng
  • Ludwig Kuznia
    • Categories Integer Programming, Stochastic Programming Tags , , , , ,

    In this paper, we study chance constrained mixed integer program with consideration of recourse decisions and their incurred cost, developed on a finite discrete scenario set. Through studying a non-traditional bilinear mixed integer formulation, we derive its linear counterparts and show that they could be stronger than existing linear formulations. We also develop a variant … Read more

    K-Adaptability in Two-Stage Robust Binary Programming

  • Grani A. Hanasusanto
  • Daniel Kuhn
  • Wolfram Wiesemann
    • Categories Integer Programming, Robust Optimization Tags , ,

    Over the last two decades, robust optimization has emerged as a computationally attractive approach to formulate and solve single-stage decision problems affected by uncertainty. More recently, robust optimization has been successfully applied to multi-stage problems with continuous recourse. This paper takes a step towards extending the robust optimization methodology to problems with integer recourse, which … 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

    Mathematical Programming techniques in Water Network Optimization

  • Cristiana Bragalli
  • Claudia D'Ambrosio
  • Andrea Lodi
  • Sven Wiese
    • Categories (Mixed) Integer Nonlinear Programming, Civil and Environmental Engineering Tags , , ,

    In this article we survey mathematical programming approaches to problems in the field of water network optimization. Predominant in the literature are two different, but related problem classes. One can be described by the notion of network design, while the other is more aptly termed by network operation. The basic underlying model in both cases … Read more