Integer Programming

Convergence of Finite-Dimensional Approximations for Mixed-Integer Optimization with Differential Equations

  • Falk M. Hante
  • Martin Schmidt
    • Categories (Mixed) Integer Nonlinear Programming, Nonlinear Optimization, Systems governed by Differential Equations Optimization Tags , , , ,

    We consider a direct approach to solve mixed-integer nonlinear optimization problems with constraints depending on initial and terminal conditions of an ordinary differential equation. In order to obtain a finite-dimensional problem, the dynamics are approximated using discretization methods. In the framework of general one-step methods, we provide sufficient conditions for the convergence of this approach … Read more

    Consistency for 0-1 programming

  • Danial Davarnia
  • John Hooker
    • Categories Cutting Plane Approaches, Integer Programming

    Concepts of consistency have long played a key role in constraint programming but never developed in integer programming (IP). Consistency nonetheless plays a role in IP as well. For example, cutting planes can reduce backtracking by achieving various forms of consistency as well as by tightening the linear programming (LP) relaxation. We introduce a type … Read more

    Generating feasible points for mixed-integer convex optimization problems by inner parallel cuts

  • Christoph Neumann
  • Oliver Stein
    • Categories (Mixed) Integer Nonlinear Programming, Cutting Plane Approaches Tags , , ,

    In this article we introduce an inner parallel cutting plane method (IPCP) to compute good feasible points along with valid cutting planes for mixed-integer convex optimization problems. The method iteratively generates polyhedral outer approximations of an enlarged inner parallel set (EIPS) of the continuously relaxed feasible set. This EIPS possesses the crucial property that any … Read more

    Sparse and Smooth Signal Estimation: Convexification of L0 Formulations

  • Alper Atamturk
  • Andrés Gómez
  • Shaoning Han
    • Categories (Mixed) Integer Nonlinear Programming Tags , , , ,

    Signal estimation problems with smoothness and sparsity priors can be naturally modeled as quadratic optimization with L0-“norm” constraints. Since such problems are non-convex and hard-to-solve, the standard approach is, instead, to tackle their convex surrogates based on L1-norm relaxations. In this paper, we propose new iterative conic quadratic relaxations that exploit not only the L0-“norm” … Read more

    Scoring positive semidefinite cutting planes for quadratic optimization via trained neural networks

  • Radu Baltean-Lugojan
  • Pierre Bonami
  • Ruth Misener
  • Andrea Tramontani
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization, Quadratic Programming Tags , , , , ,

    Semidefinite programming relaxations complement polyhedral relaxations for quadratic optimization, but global optimization solvers built on polyhedral relaxations cannot fully exploit this advantage. This paper develops linear outer-approximations of semidefinite constraints that can be effectively integrated into global solvers. The difference from previous work is that our proposed cuts are (i) sparser with respect to the … Read more

    A random search method for finding ‘K ≥ 2’ number of ranked optimal solution to an assignment problem

  • Ali Al-Hasani
  • Andrew C. Eberhard
  • Masar Al-Rabeeah
  • Santosh Kumar
    • Categories 0-1 Programming, Integer Programming

    A need for an optimal solution for a given mathematical model is well known and many solution approaches have been developed to identify efficiently an optimal solution in a given situation. For example, one such class of mathematical models with industrial applications have been classified as mathematical programming models (MPM). The main idea behind these … Read more

    Strong IP Formulations Need Large Coefficients

  • Christopher Hojny
    • Categories 0-1 Programming, Integer Programming Tags , , ,

    The development of practically well-behaving integer programming formulations is an important aspect of solving linear optimization problems over a set $X \subseteq \{0,1\}^n$. In practice, one is often interested in strong integer formulations with additional properties, e.g., bounded coefficients to avoid numerical instabilities. This article presents a lower bound on the size of coefficients in … Read more

    Chvatal rank in binary polynomial optimization

  • Alberto Del Pia
  • Silvia Di Gregorio
    • Categories 0-1 Programming, Cutting Plane Approaches, Global Optimization Theory Tags , , , , ,

    Recently, several classes of cutting planes have been introduced for binary polynomial optimization. In this paper, we present the first results connecting the combinatorial structure of these inequalities with their Chvatal rank. We show that almost all known cutting planes have Chvatal rank 1. All these inequalities have an associated hypergraph that is beta-acyclic, thus, … Read more

    Compact Disjunctive Approximations to Nonconvex Quadratically Constrained Programs

  • Hongbo Dong
  • Yunqi Luo
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Theory, Second-Order Cone Programming

    Decades of advances in mixed-integer linear programming (MILP) and recent development in mixed-integer second-order-cone programming (MISOCP) have translated very mildly to progresses in global solving nonconvex mixed-integer quadratically constrained programs (MIQCP). In this paper we propose a new approach, namely Compact Disjunctive Approximation (CDA), to approximate nonconvex MIQCP to arbitrary precision by convex MIQCPs, which … Read more

    A branch and price algorithm for the resource constrained home health care vehicle routing problem

  • Neda Tanoumand
  • Tonguç Ünlüyurt
    • Categories Integer Programming, Linear Programming Tags , , ,

    We consider the vehicle routing problem with resource constraints motivated by a home health care application. We propose a branch and price algorithm to solve the problem. In our problem, we consider different types of patients that require a nurse or a health aid or both. The patients can be serviced by the appropriate vehicles … Read more