Cutting Plane Approaches

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

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

Polynomial-Time Algorithms for Setting Tight Big-M Coefficients in Transmission Expansion Planning with Disconnected Buses

Categories Combinatorial Optimization, Cutting Plane Approaches, Energy Tags , , ,

The increasing penetration of renewable energy and rising electricity demand are driving the need to integrate new buses and transmission lines into transmission grids. These trends are reshaping transmission expansion planning (TEP), motivating the development of effective methodologies to manage the resulting complexity. This paper introduces the longest shortest-path connection (LSPC) algorithm, a graph-based method … Read more

Energy-efficient Timetables for Railway Traffic: Incorporating DC Power Models

Categories (Mixed) Integer Nonlinear Programming, Cutting Plane Approaches, Transportation Tags , , ,

Efficient operation of underground railway systems is critical not only for maintaining punctual service but also for minimizing energy consumption, a key factor in reducing operational costs and environmental impact. To evaluate the energy consumption of the timetables, this paper delves into the development of mathematical models to accurately represent energy dynamics within the underground … Read more

Optimizing with Column Generation: Advanced Branch-Cut-and-Price Algorithms (Part I)

Categories Cutting Plane Approaches, Integer Programming

We are excited to present the early release of Part I of our book “Optimizing with Column Generation: advanced Branch-Cut-and-Price Algorithms”. While the book’s ultimate goal, as suggested by its subtitle, is to describe cutting-edge techniques in these algorithms, this objective is primarily addressed in the forthcoming Part II. However, we feel that the completed … Read more

Machine Learning for Optimization-Based Separation: the Case of Mixed-Integer Rounding Cuts

Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches

Mixed-Integer Rounding (MIR) cuts are effective at improving the dual bound in Mixed-Integer Linear Programming (MIP). However, in practice, MIR cuts are separated heuristically rather than using optimization as the latter is prohibitively expensive. We present a hybrid cut generation framework in which we train a Machine Learning (ML) model to inform cut generation for … Read more

Incorporating Service Reliability in Multi-depot Vehicle Scheduling: A Chance-Constrained Approach

Categories Cutting Plane Approaches, Stochastic Programming, Transportation Tags , , ,

The multi-depot vehicle scheduling problem (MDVSP) is a critical planning challenge for transit agencies. We introduce a novel approach to MDVSP by incorporating service reliability through chance-constrained programming (CCP), targeting the pivotal issue of travel time uncertainty and its impact on transit service quality. Our model guarantees service reliability measured by on-time performance (OTP), a … Read more

New cuts and a branch-cut-and-price model for the Multi Vehicle Covering Tour Problem

Categories Combinatorial Optimization, Cutting Plane Approaches, Integer Programming Tags , , , ,

The Multi-Vehicle Covering Tour Problem (m-CTP) involves a graph in which the set of vertices is partitioned into a depot and three distinct subsets representing customers, mandatory facilities, and optional facilities. Each customer is linked to a specific subset of optional facilities that define its coverage set. The goal is to determine a set of … Read more

Using Disjunctive Cuts in a Branch-and-Cut Method to Solve Convex Integer Nonlinear Bilevel Problems

Categories (Mixed) Integer Nonlinear Programming, Bilevel Optimization, Cutting Plane Approaches Tags , , ,

We present a branch-and-cut method for solving convex integer nonlinear bilevel problems, i.e., bilevel models with nonlinear but jointly convex objective functions and constraints in both the upper and the lower level. To this end, we generalize the idea of using disjunctive cuts to cut off integer-feasible but bilevel-infeasible points. These cuts can be obtained … Read more

Set System Approximation for Binary Integer Programs: Reformulations and Applications

Categories 0-1 Programming, Cutting Plane Approaches, Integer Programming Tags , , , ,

Covering and elimination inequalities are central to combinatorial optimization, yet their role has largely been studied in problem-specific settings or via no-good cuts. This paper introduces a unified perspective that treats these inequalities as primitives for set system approximation in binary integer programs (BIPs). We show that arbitrary set systems admit tight inner and outer … Read more

On Rank-Monotone Graph Operations and Minimal Obstruction Graphs for the Lovász-Schrijver SDP Hierarchy

Categories Cutting Plane Approaches, Polyhedra, Semi-definite Programming

We study the lift-and-project rank of the stable set polytopes of graphs with respect to the Lovász-Schrijver SDP operator LS_+, with a particular focus on finding and characterizing the smallest graphs with a given LS_+-rank (the least number of iterations of the LS_+ operator on the fractional stable set polytope to compute the stable set … Read more