Integer Programming

On Perspective Functions and Vanishing Constraints in Mixed-Integer Nonlinear Optimal Control

  • Michael N. Jung
  • Christian Kirches
  • Sebastian Sager
    • Categories (Mixed) Integer Nonlinear Programming, Systems governed by Differential Equations Optimization Tags ,

    Logical implications appear in a number of important mixed-integer nonlinear optimal control problems (MIOCPs). Mathematical optimization offers a variety of different formulations that are equivalent for boolean variables, but result in different relaxations. In this article we give an overview over a variety of different modeling approaches, including outer versus inner convexification, generalized disjunctive programming, … Read more

    Automatic Dantzig-Wolfe Reformulation of Mixed Integer Programs

  • Martin Bergner
  • Alberto Caprara
  • Alberto Ceselli
  • Fabio Furini
  • Marco E. Lübbecke
  • Enrico Malaguti
  • Emiliano Traversi
    • Categories (Mixed) Integer Linear Programming Tags , , , , ,

    Dantzig-Wolfe decomposition (or reformulation) is well-known to provide strong dual bounds for specially structured mixed integer programs (MIPs). However, the method is not implemented in any state-of-the-art MIP solver as it is considered to require structural problem knowledge and tailoring to this structure. We provide a computational proof-of-concept that the reformulation can be automated. That … Read more

    Threshold Boolean Form for Joint Probabilistic Constraints with Random Technology Matrix

  • Alexander Kogan
  • Miguel A. Lejeune
    • Categories (Mixed) Integer Nonlinear Programming, Data-Mining, Stochastic Programming Tags , , , , ,

    We develop a new modeling and exact solution method for stochastic programming problems that include a joint probabilistic constraint in which the multirow random technology matrix is discretely distributed. We binarize the probability distribution of the random variables in such a way that we can extract a threshold partially defined Boolean function (pdBf) representing the … Read more

    An Outer-Inner Approximation for separable MINLPs

  • Pierre Bonami
  • Hassan L. Hijazi
  • Adam Ouorou
    • Categories (Mixed) Integer Nonlinear Programming, Optimization Software and Modeling Systems Tags , ,

    A common structure in convex mixed-integer nonlinear programs is separable nonlinear functions. In the presence of such structures, we propose three improvements to the outer approximation algorithms. The first improvement is a simple extended formulation, the second is a refined outer approximation, and the third is a heuristic inner approximation of the feasible region. These … Read more

    Approximating the solution for the multiparametric 0-1-mixed integer linear programming problem with interval data

  • Alejandro Crema
  • Fernando Crema
  • Edgar Hugo Peraza
    • Categories (Mixed) Integer Linear Programming Tags , ,

    In this paper we present algorithms to approximate the solution for the multiparametric 0-1-mixed integer linear programming problem relative to the objective function. We consider the uncertainty for the parameters that de fine the cost vector corresponding to a subset of 0-1-variables by assuming that each parameter belongs to a known interval. We suppose that we … Read more

    On valid inequalities for quadratic programming with continuous variables and binary indicators

  • Hongbo Dong
  • Jeff Linderoth
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Theory, Quadratic Programming Tags ,

    In this paper we study valid inequalities for a fundamental set that involves a continuous vector variable x in [0,1]^n, its associated quadratic form x x’ and its binary indicators. This structure appears when deriving strong relaxations for mixed integer quadratic programs (MIQPs). We treat valid inequalities for this set as lifted from QPB, which … Read more

    A unified mixed-integer programming model for simultaneous fluence weight and aperture optimization in VMAT, Tomotherapy, and Cyberknife

  • Kerem Akartunali
  • Vicky Mak-Hau
  • Thu Tran
    • Categories Biomedical Applications, Integer Programming

    In this paper, we propose and study a unified mixed-integer programming model that simultaneously optimizes fluence weights and multi-leaf collimator (MLC) apertures in the treatment planning optimization of VMAT, Tomotherapy, and CyberKnife. The contribution of our model is threefold: i. Our model optimizes the fluence and MLC apertures simultaneously for a given set of control … Read more

    Mixed Integer Linear Programming Formulation Techniques

  • Juan Pablo Vielma
    • Categories (Mixed) Integer Linear Programming

    A wide range of problems can be modeled as Mixed Integer Linear Programming (MIP) problems using standard formulation techniques. However, in some cases the resulting MIP can be either too weak or too large to be effectively solved by state of the art solvers. In this survey we review advanced MIP formulation techniques that result … Read more