Cutting Plane Approaches

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

  • Behnam Jabbari Marand
  • Adolfo Escobedo
    • Categories Combinatorial Optimization, Cutting Plane Approaches, Energy Tags , , ,

    The increasing penetration of renewable energy into power systems necessitates the development of effective methodologies to integrate initially disconnected generation sources into the grid. This paper introduces the Longest Shortest-Path-Connection (LSPC) algorithm, a graph-based method to enhance the mixed-integer linear programming disjunctive formulation of Transmission Expansion Planning (TEP) using valid inequalities (VIs). Traditional approaches for … Read more

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

  • Tobias Kuen
  • Robert Burlacu
  • Patrick Gemander
  • Jorge Weston
    • 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)

  • Eduardo Uchoa
  • Artur Alves Pessoa
  • Lorenza Moreno
    • 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

  • Oscar Guaje
  • Aleksandr M. Kazachkov
  • Elias B. Khalil
    • 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

  • Margarita P Castro
  • Merve Bodur
  • Amer Shalaby
    • 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

  • Bruno Oliveira
  • Artur Alves Pessoa
  • Marcos Roboredo
    • 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

  • Horländer Andreas
  • Ivana Ljubić
  • Martin Schmidt
    • Categories (Mixed) Integer Nonlinear Programming, 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 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 by … Read more

    Binary Integer Program Reformulation: A Set System Approximation Approach

  • Ningji Wei
    • Categories 0-1 Programming, Cutting Plane Approaches, Integer Programming Tags , , , ,

    This paper presents a generic reformulation framework for binary integer programs (BIPs) that does not impose additional specifications on the objective function or constraints. To enable this generality, we introduce a set system approximation theory designed to identify the tightest inner and outer approximations for any binary solution space using special types of set systems. … Read more

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

  • Yu Hin (Gary) Au
  • Levent Tunçel
    • 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

    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