Integer Programming Models for Round Robin Tournaments

Round robin tournaments are omnipresent in sport competitions and beyond. We propose two new integer programming formulations for scheduling a round robin tournament, one of which we call the matching formulation. We analytically compare their linear relaxations with the linear relaxation of a well-known traditional formulation. We find that the matching formulation is stronger than … Read more

Vehicle Routing with Heterogeneous Time Windows

We consider a novel variant of the heterogeneous vehicle routing problem (VRP) in which each customer has different availability time windows for every vehicle. In particular, this covers our motivating application of planning daily delivery tours for a single vehicle, where customers can be available at different times each day. The existing literature on heterogeneous … Read more

The complexity of branch-and-price algorithms for the capacitated vehicle routing problem with stochastic demands

The capacitated vehicle routing problem with stochastic demands (CVRPSD) is a variant of the deterministic capacitated vehicle routing problem where customer demands are random variables. While the most successful formulations for several deterministic vehicle-routing problem variants are based on a set-partitioning formulation, adapting such formulations for the CVRPSD under mild assumptions on the demands remains … Read more

The Pickup and Delivery Problem with Time Windows and Incompatibility Constraints in Cold Chain Transportation

This study investigates a new variant of the pickup and delivery problem with time windows (PDPTW) applied in cold chain transportation, which quantifies the effect of time on the quality of perishable products. Multiple commodities with incompatibility constraints are considered, where some types of products cannot be transported in a vehicle simultaneously due to their … Read more

Branch-and-price for clash-free periodic supply vessel planning problem with split delivery and variable service time

Efficient scheduling and routing of vessels are crucial in the oil and gas industries. In this paper, we consider a periodic supply vessel planning problem in which the weekly demands at multiple offshore facilities are satisfied with a fleet of heterogeneous vessels. Preemptive service at the base, variable service at facilities, and split delivery are … Read more

A Route-Based Algorithm for the Electric Vehicle Routing Problem with Multiple Technologies

Electric vehicles are seen as a pragmatic way of reducing emissions. In freight transportation, they prove to be appealing also in terms of costs, if proper planning algorithms are designed. We consider a variant of the electric vehicle routing problem: a fleet of identical vehicles of limited capacity needs to visit a set of customers … Read more

Efficient MIP Techniques for Computing the Relaxation Complexity

The relaxation complexity rc(X) of the set of integer points X contained in a polyhedron is the minimal number of inequalities needed to formulate a linear optimization problem over X without using auxiliary variables. Besides its relevance in integer programming, this concept has interpretations in aspects of social choice, symmetric cryptanalysis, and machine learning. We … Read more

Integer programming column generation: Accelerating branch-and-price using a novel pricing scheme for finding high-quality solutions in set covering, packing, and partitioning problems

Large-neighbourhood search (LNS) heuristics are important mathematical programming techniques that search for primal feasible solutions by solving an auxiliary problem with a restricted feasible region. Extending such powerful generic LNS heuristics to the branch- and-price context is inherently challenging. The most prominent challenges arise from the fact that in branch-and-price algorithms, columns are generated with … Read more

A Branch-and-Price Algorithm for the Vehicle Routing Problem with Drones

This paper considers a new variant of the vehicle routing problem with drones (VRPD), where multiple vehicles and drones work collaboratively to serve customers. Several practical constraints such as customers’ delivery deadlines and drones’ energy capacity are considered. Different from existing studies, we treat the number of drones taken by each vehicle as a decision … Read more

The SCIP Optimization Suite 8.0

The SCIP Optimization Suite provides a collection of software packages for mathematical optimization centered around the constraint integer programming framework SCIP. This paper discusses enhancements and extensions contained in version 8.0 of the SCIP Optimization Suite. Major updates in SCIP include improvements in symmetry handling and decomposition algorithms, new cutting planes, a new plugin type … Read more