Integer Programming

On Tractable Convex Relaxations of Standard Quadratic Optimization Problems under Sparsity Constraints

Categories (Mixed) Integer Nonlinear Programming, Quadratic Programming, Semi-definite Programming Tags , , , ,

Standard quadratic optimization problems (StQPs) provide a versatile modelling tool in various applications. In this paper, we consider StQPs with a hard sparsity constraint, referred to as sparse StQPs. We focus on various tractable convex relaxations of sparse StQPs arising from a mixed-binary quadratic formulation, namely, the linear optimization relaxation given by the reformulation-linearization technique, … Read more

Strengthened MIP Formulations for the Liver Region Redesign Models of Akshat et al.

Categories Integer Programming

Liver transplantation has been a critical issue in the U.S. healthcare system for decades, and the region redesign aims to ameliorate this issue. This paper revisits two mixed integer programming (MIP) formulations of the liver region redesign problem proposed by Akshat et al. We study their first formulation considering two different modeling approaches: one compact … Read more

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

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

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

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

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

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

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

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