Integer Programming

A Polyhedral Study of the Integrated Minimum-Up/-Down Time and Ramping Polytope

  • Yongpei Guan
  • Kai Pan
    • Categories Applications - Science and Engineering, Cutting Plane Approaches

    In this paper, we consider the polyhedral structure of the integrated minimum-up/-down time and ramping polytope for the unit commitment problem. Our studied generalized polytope includes minimum-up/-down time constraints, generation ramp-up/-down rate constraints, logical constraints, and generation upper/lower bound constraints. We derive strong valid inequalities by utilizing the structures of the unit commitment problem, and … Read more

    New computer-based search strategies for extreme functions of the Gomory–Johnson infinite group problem

  • Matthias Köppe
  • Yuan Zhou
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches Tags , ,

    We describe new computer-based search strategies for extreme functions for the Gomory–Johnson infinite group problem. They lead to the discovery of new extreme functions, whose existence settles several open questions. ArticleDownload View PDF

    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