WB3 - Decomposition Techniques

We develop a strong MILP formulation and a Benders‑based algorithm for assortment optimization under multi‑purchase ranked‑list models. We propose a set of acceleration techniques for efficient subproblem solutions, and a greedy heuristic improves scalability. Our computational results demonstrate significant computational speedups over existing solution approaches, efficiently solving large‑scale instances.

The Resource-Constrained Project Scheduling Problem (RCPSP) is a fundamental NP-hard problem arising in project management, manufacturing, and resource planning. Despite decades of research, computing tight lower bounds for hard instances remains a major challenge. We address this gap with a branch-and-price framework built on an original decomposition scheme that structurally strengthens lower bound computations.
The framework combines tailored pricing problems with a bound computation technique that exploits problem-specific properties, leading to tighter relaxations than classical formulations. A hybrid branching strategy leverages the distinct roles of model variables alongside custom post-decision propagation through the network, enabling effective search space exploration while producing high-quality feasible solutions.
Computational experiments on PSPLIB instances demonstrate that the proposed approach establishes new best lower bounds on hard instances and yields competitive upper bounds, outperforming state-of-the-art exact methods.

We automate the equivalence between linear programs using a filtering algorithm and two constrained models, relying on two matrix permutation and scaling theorems that we have established. Our best methods depend on the type of problem and solve at least 86.05% of the 774 instances in less than one minute.

Operating large-scale ride-sharing services requires solving the dynamic Dial-a-Ride Problem (DARP) in real time, constantly balancing routing efficiency against strict computational latency limits. Traditional batch-based dispatching relies on fixed intervals, which inherently introduce response delays and fail to adapt to varying computational loads. To address this, we introduce a novel anytime re-optimization framework driven by a flexible rolling-horizon strategy, where epoch lengths dynamically adapt to the actual computation time rather than predetermined batching intervals. At the core of this framework is an anytime column generation (A-CG) algorithm designed to prioritize early solution improvement. By systematically reusing information across consecutive planning epochs, the algorithm makes high-frequency re-optimization computationally tractable. The method also includes a simple lightweight vehicle rebalancing strategy to improve coverage in high-demand areas. Computational experiments on large-scale instances derived from New York City taxi data demonstrate that the proposed approach achieves a strong balance between responsiveness and service quality—reducing customer waiting times while maintaining short per-update computation times, even at demand levels of up to 30,000 requests per hour.