(Mixed) Integer Linear Programming

Improved Approximation Algorithms for Orthogonally Constrained Problems Using Semidefinite Optimization

  • Ryan Cory-Wright
  • Jean Pauphilet
    • Categories (Mixed) Integer Linear Programming, Approximation Algorithms, Semi-definite Programming

    Building on the blueprint from Goemans and Williamson (1995) for the Max-Cut problem, we construct a polynomial-time approximation algorithm for orthogonally constrained quadratic optimization problems. First, we derive a semidefinite relaxation and propose a randomized rounding algorithm to generate feasible solutions from the relaxation. Second, we derive constant-factor approximation guarantees for our algorithm. When optimizing … Read more

    Proximity results in convex mixed-integer programming

  • Burak Kocuk
  • Diego Moran Ramirez
    • Categories (Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming, Cone Programming Tags , , , ,

    We study proximity (resp. integrality gap), that is, the distance (resp. difference) between the optimal solutions (resp. optimal values) of convex integer programs (IP) and the optimal solutions (resp. optimal values) of their continuous relaxations. We show that these values can be upper bounded in terms of the recession cone of the feasible region of … Read more

    Solving Multi-Follower Mixed-Integer Bilevel Problems with Binary Linking Variables

  • Vladimir Stadnichuk
  • Arie M.C.A. Koster
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches, Network Optimization Tags , , , ,

    We study multi-follower bilevel optimization problems with binary linking variables where the second level consists of many independent integer-constrained subproblems. This problem class not only generalizes many classical interdiction problems but also arises naturally in many network design problems where the second-level subproblems involve complex routing decisions of the actors involved. We propose a novel … Read more

    Neural Embedded Mixed-Integer Optimization for Location-Routing Problems

  • Waquar Kaleem
  • Anirudh Subramanyam
    • Categories (Mixed) Integer Linear Programming, Facility Planning and Design, Production and Logistics Tags , , ,

    We present a novel framework that combines machine learning with mixed-integer optimization to solve the Capacitated Location-Routing Problem (CLRP). The CLRP is a classical yet NP-hard problem that integrates strategic facility location with operational vehicle routing decisions, aiming to simultaneously minimize both fixed and variable costs. The proposed method first trains a permutationally invariant neural … Read more

    Mixed-Integer Bilevel Optimization with Nonconvex Quadratic Lower-Level Problems: Complexity and a Solution Method

  • Immanuel M. Bomze
  • Martin Schmidt
  • Horländer Andreas
    • Categories (Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming Tags , , ,

    We study bilevel problems with a convex quadratic mixed-integer upper-level, integer linking variables, and a nonconvex quadratic, purely continuous lower-level problem. We prove $\Sigma_p^2$-hardness of this class of problems, derive an iterative lower- and upper-bounding scheme, and show its finiteness and correctness in the sense that it computes globally optimal points or proves infeasibility of … Read more

    On parametric formulations for the Asymmetric Traveling Salesman Problem

  • Gustavo Angulo
  • Diego Moran Ramirez
    • Categories (Mixed) Integer Linear Programming, Linear Programming, Polyhedra

    The traveling salesman problem is a widely studied classical combinatorial problem for which there are several integer linear formulations. In this work, we consider the Miller-Tucker-Zemlin (MTZ), Desrochers-Laporte (DL) and Single Commodity Flow (SCF) formulations. We argue that the choice of some parameters of these formulations is arbitrary and, therefore, there are families of formulations … Read more

    An Efficient Algorithm to the Integrated Shift and Task Scheduling Problem

  • G S R Murthy
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Scheduling Tags , , , , ,

    Abstract   This paper deals with operational models for integrated shift and task scheduling problem. Staff scheduling problem is a special case of this with staff requirements as given input to the problem. Both problems become hard to solve when the problems are considered with flexible shifts. Current literature on these problems leaves good scope … Read more

    Approximating the Gomory Mixed-Integer Cut Closure Using Historical Data

  • Berkay Becu
  • Santanu S. Dey
  • Feng Qiu
  • Alinson S. Xavier
    • Categories (Mixed) Integer Linear Programming

    Many operations related optimization problems involve repeatedly solving similar mixed integer linear programming (MILP) instances with the same constraint matrix but differing objective coefficients and right-hand-side values. The goal of this paper is to generate good cutting-planes for such instances using historical data. Gomory mixed integer cuts (GMIC) for a general MILP can be parameterized … Read more

    Accelerating Benders decomposition for solving a sequence of sample average approximation replications

  • Harshit Kothari
  • James R. Luedtke
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Stochastic Programming

    Sample average approximation (SAA) is a technique for obtaining approximate solutions to stochastic programs that uses the average from a random sample to approximate the expected value that is being optimized. Since the outcome from solving an SAA is random, statistical estimates on the optimal value of the true problem can be obtained by solving … Read more

    Cut-based Conflict Analysis in Mixed Integer Programming

  • Gioni Mexi
  • Felipe Serrano
  • Timo Berthold
  • Ambros Gleixner
  • jakobnordstrom
    • Categories (Mixed) Integer Linear Programming, 0-1 Programming, Integer Programming Tags , , , , ,

    For almost two decades, mixed integer programming (MIP) solvers have used graph- based conflict analysis to learn from local infeasibilities during branch-and-bound search. In this paper, we improve MIP conflict analysis by instead using reasoning based on cuts, inspired by the development of conflict-driven solvers for pseudo- Boolean optimization. Phrased in MIP terminology, this type … Read more