Combinatorial Optimization

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

    Machine Learning Algorithms for Assisting Solvers for Constraint Satisfaction Problems

  • Morteza Kimiaei
  • Vyacheslav Kungurtsev
    • Categories Applications - OR and Management Sciences, Combinatorial Optimization, Optimization in Data Science Tags , , , , , , , , , ,

    This survey proposes a unifying conceptual framework and taxonomy that systematically integrates Machine Learning (ML) and Reinforcement Learning (RL) with classical paradigms for Constraint Satisfaction and Boolean Satisfiability solving. Unlike prior reviews that focus on individual applications, we organize the literature around solver architecture, linking each major phase—constraint propagation, heuristic decision-making, conflict analysis, and meta-level … 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

    Data-Driven Optimization for Meal Delivery: A Reinforcement Learning Approach for Order-Courier Assignment and Routing at Meituan

  • Ramon Auad
  • Felipe Lagos
  • Tomas Lagos
    • Categories Dynamic Programming, Meta Heuristics, Transportation Tags

    The rapid growth of online meal delivery has introduced complex logistical challenges, where platforms must dynamically assign orders to couriers while accounting for demand uncertainty, courier autonomy, and service efficiency. Traditional dispatching methods, often focused on short-term cost minimization, fail to capture the long-term implications of assignment decisions on system-wide performance. This paper presents a … Read more

    Political districting to maximize whole counties

  • Maral Shahmizad
  • Austin Buchanan
    • Categories Applications - OR and Management Sciences, Combinatorial Optimization, Integer Programming Tags , , ,

    We consider a fundamental question in political districting: How many counties can be kept whole (i.e., not split across multiple districts), while satisfying basic criteria like contiguity and population balance? To answer this question, we propose integer programming techniques based on combinatorial Benders decomposition. The main problem decides which counties to keep whole, and the … Read more

    Discovering Heuristics with Large Language Models (LLMs) for Mixed-Integer Programs: Single-Machine Scheduling

  • I. Esra Buyuktahtakin Toy
    • Categories (Mixed) Integer Linear Programming, Combinatorial Optimization, Meta Heuristics Tags , , , , , , ,

    TitleDiscovering Heuristics with Large Language Models (LLMs) for Mixed-Integer Programs: Single-Machine Scheduling Authorsİbrahim Oğuz Çetinkaya^1; İ. Esra Büyüktahtakın^1*; Parshin Shojaee^2; Chandan K. Reddy^2 Affiliations^1 Grado Department of Industrial and Systems Engineering, Virginia Tech, Blacksburg, VA, USA^2 Department of Computer Science, Virginia Tech, Arlington, VA, USA Abstract: Our study contributes to the scheduling and combinatorial optimization … Read more

    Consolidation in Crowdshipping with Scheduled Transfer Lines: A Surrogate-Based Network Design Framework

  • Ramazan Çevik
  • Ali Şardağ
  • Barış Yıldız
    • Categories Combinatorial Optimization, Optimization in Data Science, Transportation Tags , , ,

    Abstract: Crowdshipping has gained attention as an emerging delivery model thanks to advantages such as flexibility and an asset-light structure. Yet, it chronically suffers from a lackof mechanisms to create and exploit consolidation opportunities, limiting its efficiency and scalability. This work contributes to the literature in two ways: first, by introducing a novel consolidation concept … Read more

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

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

    We study the vehicle routing problem with stochastic demands (VRPSD), an important variant of the classical capacitated vehicle routing problem in which customer demands are modeled as random variables. We develop the first algorithm for the VRPSD in the case where the demands are given by an empirical probability distribution of scenarios — a data-driven … 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