Integer Programming

Benchmarking Piecewise Linear Relaxations for MINLPs: A Computational Study Based on the Open-Source Framework PWL-T-Rex

  • Kristin Braun
  • Robert Burlacu
    • Categories (Mixed) Integer Nonlinear Programming Tags , , ,

    Solving mixed-integer nonlinear problems by means of piecewise linear relaxations has emerged as a reasonable alternative to the commonly used spatial branch-and-bound. These relaxations have been modeled by various mixed-integer models in recent decades. The idea is to exploit the availability of mature solvers for mixed-integer problems. In this work, we implement a framework that … Read more

    Solving Hard Bi-objective Knapsack Problems Using Deep Reinforcement Learning

  • Hadi Charkhgard
    • Categories Approximation Algorithms, Integer Programming Tags , , ,

    We study a class of bi-objective integer programs known as bi-objective knapsack problems (BOKPs). Our research focuses on the development of innovative exact and approximate solution methods for BOKPs by synergizing algorithmic concepts from two distinct domains: multi-objective integer programming and (deep) reinforcement learning. While novel reinforcement learning techniques have been applied successfully to single-objective … Read more

    A novel Pareto-optimal cut selection strategy for Benders Decomposition

  • Lukas Glomb
  • Frauke Liers
  • Florian Rösel
    • Categories (Mixed) Integer Linear Programming Tags ,

    Decomposition methods can be used to create efficient solution algorithms for a wide range of optimization problems. For example, Benders Decomposition can be used to solve scenario-expanded two-stage stochastic optimization problems effectively. Benders Decomposition iteratively generates Benders cuts by solving a simplified version of an optimization problem, the so-called subproblem. The choice of the generated … Read more

    An Integer Programming Approach To Subspace Clustering With Missing Data

  • Akhilesh Soni
  • Jeff Linderoth
  • James R. Luedtke
  • Daniel Pimentel-Alarcon
    • Categories Data Science Algorithms, Integer Programming Tags , ,

    In the Subspace Clustering with Missing Data (SCMD) problem, we are given a collection of n partially observed d-dimensional vectors. The data points are assumed to be concentrated near a union of low-dimensional subspaces. The goal of SCMD is to cluster the vectors according to their subspace membership and recover the underlying basis, which can … Read more

    Resilient Relay Logistics Network Design: A k-Shortest Path Approach

  • Onkar Anand Kulkarni
  • Mathieu Dahan
    • Categories (Mixed) Integer Linear Programming, Facility Planning and Design, Production and Logistics Tags , , , ,

    Problem definition: We study the problem of designing large-scale resilient relay logistics hub networks. We propose a model of k-Shortest Path Network Design, which aims to improve a network’s efficiency and resilience through its topological configuration, by locating relay logistics hubs to connect each origin-destination pair with k paths of minimum lengths, weighted by their … Read more

    DeLuxing: Deep Lagrangian Underestimate Fixing for Column-Generation-Based Exact Methods

  • Yu Yang
    • Categories Branch and Cut Algorithms, Integer Programming, Transportation

    In this paper, we propose an innovative variable fixing strategy called deep Lagrangian underestimate fixing (DeLuxing). It is a highly effective approach for removing unnecessary variables in column-generation (CG)-based exact methods used to solve challenging discrete optimization problems commonly encountered in various industries, including vehicle routing problems (VRPs). DeLuxing employs a novel linear programming (LP) … Read more

    Affine FR : an effective facial reduction algorithm for semidefinite relaxations of combinatorial problems

  • Hao Hu
  • Boshi Yang
    • Categories 0-1 Programming, Convex Optimization, Semi-definite Programming

    We develop a new method called \emph{affine FR} for recovering Slater’s condition for semidefinite programming (SDP) relaxations of combinatorial optimization (CO) problems. Affine FR is a user-friendly method, as it is fully automatic and only requires a description of the problem. We provide a rigorous analysis of differences between affine FR and the existing methods. … Read more

    A hybrid branch-and-bound and interior-point algorithm for stochastic mixed-integer nonlinear second-order cone programming

  • Baha Alzalg
    • Categories (Mixed) Integer Nonlinear Programming, Cutting Plane Approaches, Second-Order Cone Programming Tags , , , ,

    One of the chief attractions of stochastic mixed-integer second-order cone programming is its diverse applications, especially in engineering (Alzalg and Alioui, {\em IEEE Access}, 10:3522-3547, 2022). The linear and nonlinear versions of this class of optimization problems are still unsolved yet. In this paper, we develop a hybrid optimization algorithm coupling branch-and-bound and primal-dual interior-point … Read more

    Information Complexity of Mixed-integer Convex Optimization

  • Amitabh Basu
  • Hongyi Jiang
  • Phillip Kerger
  • Marco Molinaro
    • Categories (Mixed) Integer Nonlinear Programming, Convex and Nonsmooth Optimization, Convex Optimization Tags , , ,

    We investigate the information complexity of mixed-integer convex optimization under different types of oracles. We establish new lower bounds for the standard first-order oracle, improving upon the previous best known lower bound. This leaves only a lower order linear term (in the dimension) as the gap between the lower and upper bounds. This is derived … Read more