Integer Programming

Regularization vs. Relaxation: A convexification perspective of statistical variable selection

  • Kun Chen
  • Hongbo Dong
  • Jeff Linderoth
    • Categories (Mixed) Integer Nonlinear Programming, Linear, Cone and Semidefinite Programming, Statistics Tags , , ,

    Variable selection is a fundamental task in statistical data analysis. Sparsity-inducing regularization methods are a popular class of methods that simultaneously perform variable selection and model estimation. The central problem is a quadratic optimization problem with an $\ell_0$-norm penalty. Exactly enforcing the $\ell_0$-norm penalty is computationally intractable for larger scale problems, so different sparsity-inducing penalty … Read more

    Stronger Multi-Commodity Flow Formulations of the (Capacitated) Sequential Ordering Problem

  • Adam N. Letchford
  • Juan-José Salazar-González
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Network Optimization Tags , , , ,

    The “sequential ordering problem” (SOP) is the generalisation of the asymmetric travelling salesman problem in which there are precedence relations between pairs of nodes. Hernández & Salazar introduced a “multi-commodity flow” (MCF) formulation for a generalisation of the SOP in which the vehicle has a limited capacity. We strengthen this MCF formulation by fixing variables … Read more

    A MAX-CUT formulation of 0/1 programs

  • Jean-Bernard Lasserre
    • Categories 0-1 Programming, Approximation Algorithms, Semi-definite Programming

    We consider the linear or quadratic 0/1 program \[P:\quad f^*=\min\{ c^Tx+x^TFx : \:A\,x =\b;\:x\in\{0,1\}^n\},\] for some vectors $c\in R^n$, $b\in Z^m$, some matrix $A\in Z^{m\times n}$ and some real symmetric matrix $F\in R^{n\times n}$. We show that $P$ can be formulated as a MAX-CUT problem whose quadratic form criterion is explicit from the data of … Read more

    A New Method for Optimizing a Linear Function over the Efficient Set of a Multiobjective Integer Program

  • Natashia Boland
  • Hadi Charkhgard
  • Martin Savelsbergh
    • Categories Integer Programming, Multi-Criteria Optimization Tags , , , ,

    We present a new algorithm for optimizing a linear function over the set of efficient solutions of a multiobjective integer program MOIP. The algorithm’s success relies on the efficiency of a new algorithm for enumerating the nondominated points of a MOIP, which is the result of employing a novel criterion space decomposition scheme which (1) … Read more

    A Binarisation Heuristic for Non-Convex Quadratic Programming with Box Constraints

  • Laura Galli
  • Adam N. Letchford
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization, Quadratic Programming

    Non-convex quadratic programming with box constraints is a fundamental problem in the global optimization literature, being one of the simplest NP-hard nonlinear programs. We present a new heuristic for this problem, which enables one to obtain solutions of excellent quality in reasonable computing times. The heuristic consists of four phases: binarisation, convexification, branch-and-bound, and local … Read more

    Reoptimization Techniques for MIP Solvers

  • Gerald Gamrath
  • Jakob Witzig
  • Benjamin Hiller
    • Categories 0-1 Programming, Branch and Cut Algorithms, Problem Solving Environments Tags , , , ,

    Recently, there have been many successful applications of optimization algorithms that solve a sequence of quite similar mixed-integer programs (MIPs) as subproblems. Traditionally, each problem in the sequence is solved from scratch. In this paper we consider reoptimization techniques that try to benefit from information obtained by solving previous problems of the sequence. We focus … Read more

    Relaxations and discretizations for the pooling problem

  • Shabbir Ahmed
  • Myun-Seok Cheon
  • Santanu S. Dey
  • Akshay Gupte
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Tags , , , ,

    The pooling problem is a folklore NP-hard global optimization problem that finds applications in industries such as petrochemical refining, wastewater treatment, and mining. This paper assimilates the vast literature on this problem that is dispersed over different areas and gives unifying arguments and new insights on prevalent techniques. We also present new ideas for computing … Read more

    A mean-risk MINLP for transportation network protection

  • Akshay Gupte
  • Yongxi Huang
  • Jie Lu
    • Categories (Mixed) Integer Nonlinear Programming, Stochastic Approaches, Transportation Tags , , , ,

    This paper focuses on transportation network protection to hedge against extreme events such as earthquakes. Traditional two-stage stochastic programming has been widely adopted to obtain solutions under a risk-neutral preference through the use of expectations in the recourse function. In reality, decision makers hold different risk preferences. We develop a mean-risk two-stage stochastic programming model … Read more

    K-Adaptability in Two-Stage Distributionally Robust Binary Programming

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

    We propose to approximate two-stage distributionally robust programs with binary recourse decisions by their associated K-adaptability problems, which pre-select K candidate second-stage policies here-and-now and implement the best of these policies once the uncertain parameters have been observed. We analyze the approximation quality and the computational complexity of the K-adaptability problem, and we derive explicit … Read more

    An exact solution method for binary equilibrium problems with compensation and the power market uplift problem

  • Daniel Huppmann
  • Sauleh Siddiqui
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Game Theory Tags , , , , , ,

    We propose a novel method to fi nd Nash equilibria in games with binary decision variables by including compensation payments and incentive-compatibility constraints from non-cooperative game theory directly into an optimization framework in lieu of using first order conditions of a linearization, or relaxation of integrality conditions. The reformulation off ers a new approach to obtain and … Read more