Combinatorial Optimization

A Catalog of Formulations for the Multi-Follower Discrete Bilevel Network Design Problem

  • Vladimir Stadnichuk
    • Categories Bilevel Optimization, Branch and Cut Algorithms, Network Optimization Tags , , ,

    Network design problems increasingly arise in settings where strategic infrastructure decisions and operational routing choices are made by different actors. Such interactions are naturally modeled as bilevel problems: a network operator designs or modifies a network, while users respond by selecting routes according to their own utilities. This structure captures many applications in transportation and … Read more

    Skip or Insert? A Priori Optimization for the Vehicle Routing Problem with Time Windows and Stochastic Customers

  • Yulin Han
  • Hande Yaman
    • Categories Combinatorial Optimization, Production and Logistics, Stochastic Programming Tags , , , , , , ,

    We study an extension of the vehicle routing problem with time windows by incorporating stochastic customers, i.e., ad-hoc service requests. The uncertainty in stochastic customers is captured through scenarios. Two a priori optimization approaches, a classical and a new one lead to two different problems, both of which are modeled as scenario-based two-stage stochastic programs. … Read more

    Neural Assortment Optimization

  • Zhen Yang
    • Categories Combinatorial Optimization, Nonsmooth Optimization, Yield Management

    Assortment optimization selects a subset of items to maximize expected revenue under a discrete choice model and is widely used in revenue management and online platforms. Its combinatorial nature creates a practical tension among generality, scalability, and provable guarantees: model-specific algorithms can be strong when their structural assumptions hold, but are hard to adapt across … Read more

    Optimal Macroitem Sequences in the Precedence Constrained Knapsack Problem

  • Valerio Dose
  • Fabio Furini
  • Marco Locatelli
    • Categories Combinatorial Optimization, Graphs and Matroids, Linear Programming Tags , , ,

    The Precedence Constrained Knapsack Problem (PCKP) asks for a maximum-profit subset of items, subject to a knapsack capacity constraint and precedence constraints encoded by a directed acyclic graph. We study the structure of optimal solutions of the Linear Programming (LP) relaxation of the natural Integer Linear Programming formulation of the PCKP. We introduce the notion … Read more

    D-optimal partitioning: design of experiments under heterogeneous treatment effects

  • Jiaqi Wang
  • Weijun Xie
    • Categories Combinatorial Optimization, Nonlinear Optimization, Optimization in Data Science Tags , , , ,

    Modern experimentation in business and public policy often studies targeted interventions whose effects depend on the heterogeneous attributes of individuals. We examine heterogeneous treatment effects through the lens of optimal design of experiments, which allocates treatment decisions to maximize the precision of estimated treatment-covariate interactions. We introduce the D-optimal partitioning problem for balancing the information … Read more

    Advancing Branch-and-Price for Graph Coloring: New Pricing Strategies and Benchmark Results

  • Mingming Zheng
  • Roberto Baldacci
  • Fabio Furini
  • Qinghua Wu
    • Categories 0-1 Programming, Combinatorial Optimization, Integer Programming Tags , , ,

    This paper proposes BPCOL+, an exact branch-and-price algorithm for the Graph Coloring Problem. The algorithm is both novel and highly effective, integrating enhanced pricing strategies within Zero-Suppressed Binary Decision Diagrams (ZDDs) to efficiently solve the pricing problem associated with the maximal-stable-set-based set-covering formulation. After computing upper and lower bounds at the root node using heuristic … Read more

    Exact Approaches for the Maximum Mortality Rate Clique Problem

  • Parisa Vaghfi Mohebbi
  • Yajun Lu
  • Balabhaskar Balasundaram
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Branch and Cut Algorithms Tags , , ,

    This paper develops exact solution methods for the maximum mortality rate clique problem, which aims to identify a cluster of diseases in a comorbidity graph associated with the highest mortality rate among patients whose healthcare encounters are recorded in electronic health records. We establish the NP-hardness of the problem and propose two mixed-integer linear programming … Read more

    Objective Domain Reduction for Enhancing Solver Performance on Challenging Integer Programs

  • Aadya Bhattarai
  • Lagnajita Basu
  • Tapas Das
  • Kimia Keshanian
  • Hadi Charkhgard
    • Categories Combinatorial Optimization, Integer Programming, Transportation Tags , , , ,

    In this study, we explore how the domain of objective function values for challenging integer programs can be reduced and whether such a reduction can improve the solution process. Our work is motivated by binary search, a technique that efficiently narrows a search space by repeatedly halving it through feasibility checks. Building on this idea, … Read more

    Prophets in Parallel: Dynamic Cut Minimization in Series-Parallel Graphs

  • William Frendreiss
  • Alejandro Toriello
    • Categories Combinatorial Optimization, Dynamic Programming Tags , , ,

    We introduce a sequential version of the minimum $s$-$t$ cut problem, defined by a directed graph with source $s$ and sink $t$, and nonnegative random variables for each arc representing arc weights. We start with a working set $S = \{s\}$ and observe weight realizations for outgoing arcs from $S$ only. We choose to either … Read more