Branch and Cut Algorithms

A Combinatorial Branch-and-Bound Algorithm for the Capacitated Facility Location Problem under Strict Customer Preferences

  • Christina Büsing
  • Felix Engelhardt
  • Sophia Wrede
    • Categories Bilevel Optimization, Branch and Cut Algorithms, Combinatorial Optimization Tags , , , ,

    This work proposes a combinatorial branch-and-bound (B&B) algorithm for the capacitated facility location problem under strict customer preferences (CFLP-SCP). We use combinatorial insights into the problem structure to do preprocessing, model branching implications, enforce feasibility or prove infeasibility in each node, select variables and derive primal and dual bounds in each node of the B&B … Read more

    Branch-and-Cut for Computing Approximate Equilibria of Mixed-Integer Generalized Nash Games

  • Alois Duguet
  • Tobias Harks
  • Martin Schmidt
  • Julian Schwarz
    • Categories (Mixed) Integer Nonlinear Programming, Branch and Cut Algorithms, Game Theory Tags , , , ,

    Generalized Nash equilibrium problems with mixed-integer variables constitute an important class of games in which each player solves a mixed-integer optimization problem, where both the objective and the feasible set is parameterized by the rivals’ strategies. However, such games are known for failing to admit exact equilibria and also the assumption of all players being … Read more

    Improving Directions in Mixed Integer Bilevel Linear Optimization

  • Federico Battista
  • Ted K. Ralphs
    • Categories (Mixed) Integer Linear Programming, Bilevel Optimization, Branch and Cut Algorithms Tags , ,

    We consider the central role of improving directions in solution methods for mixed integer bilevel linear optimization problems (MIBLPs). Current state-of-the-art methods for solving MIBLPs employ the branch-and-cut framework originally developed for solving mixed integer linear optimization problems. This approach relies on oracles for two kinds of subproblems: those for checking whether a candidate pair … Read more

    On vehicle routing problems with stochastic demands — Generic integer L-shaped formulations

  • Matheus Jun Ota
  • Ricardo Fukasawa
    • Categories Branch and Cut Algorithms, Stochastic Programming, Transportation Tags , , ,

    We study a broad class of vehicle routing problems in which the cost of a route is allowed to be any nonnegative rational value computable in polynomial time in the input size. To address this class, we introduce a unifying framework that generalizes existing integer L-shaped (ILS) formulations developed for vehicle routing problems with stochastic … Read more

    Approximating value functions via corner Benders’ cuts

  • Matheus Jun Ota
  • Ricardo Fukasawa
  • Aleksandr M. Kazachkov
    • Categories Branch and Cut Algorithms, Integer Programming, Stochastic Programming Tags , , , , ,

    We introduce a novel technique to generate Benders’ cuts from a conic relaxation (“corner”) derived from a basis of a higher-dimensional polyhedron that we aim to outer approximate in a lower-dimensional space. To generate facet-defining inequalities for the epigraph associated to this corner, we develop a computationally-efficient algorithm based on a compact reverse polar formulation … Read more

    Solving the Partial Inverse Knapsack Problem

  • Eva Ley
  • Nikolas Lykourinos
  • Maximilian Merkert
  • Andreas M. Tillmann
    • Categories (Mixed) Integer Linear Programming, Bilevel Optimization, Branch and Cut Algorithms Tags , , , ,

    In this paper, we investigate the partial inverse knapsack problem, a bilevel optimization problem in which the follower solves a classical 0/1-knapsack problem with item profit values comprised of a fixed part and a modification determined by the leader. Specifically, the leader problem seeks a minimal change to given item profits such that there is … Read more

    The Minimization of the Weighted Completion Time Variance in a Single Machine: A Specialized Cutting-Plane Approach

  • Stefano Nasini
  • Rabia Nessah
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Scheduling

    This study addresses the problem of minimizing the weighted completion time variance (WCTV) in single-machine scheduling. Unlike the unweighted version, which has been extensively studied, the weighted variant introduces unique challenges due to the absence of theoretical properties that could guide the design of efficient algorithms. We propose a mathematical programming framework based on a … Read more

    A Dantzig-Wolfe Single-Level Reformulation for Mixed-Integer Linear Bilevel Optimization: Exact and Heuristic Approaches

  • Henri Lefebvre
  • Martin Schmidt
    • Categories (Mixed) Integer Linear Programming, Bilevel Optimization, Branch and Cut Algorithms Tags , , , ,

    Bilevel optimization problems arise in numerous real-world applications. While single-level reformulations are a common strategy for solving convex bilevel problems, such approaches usually fail when the follower’s problem includes integer variables. In this paper, we present the first single-level reformulation for mixed-integer linear bilevel optimization, which does not rely on the follower’s value function. Our … Read more

    A Graphical Global Optimization Framework for Parameter Estimation of Statistical Models with Nonconvex Regularization Functions

  • Danial Davarnia
    • Categories (Mixed) Integer Nonlinear Programming, Branch and Cut Algorithms, Global Optimization Theory Tags , , , ,

    Optimization problems with norm-bounding constraints appear in various applications, from portfolio optimization to machine learning, feature selection, and beyond. A widely used variant of these problems relaxes the norm-bounding constraint through Lagrangian relaxation and moves it to the objective function as a form of penalty or regularization term. A challenging class of these models uses … Read more