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
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
This paper studies a new variant of the vehicle routing problem with drones, i.e., the two-echelon vehicle routing problem with drones, where multiple vehicles and drones work collaboratively to serve customers. Drones can perform multiple back-and-forth trips when their paired vehicle stops at a customer node, forming a two-echelon network. Several practical constraints such as … Read more
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
Nested multi-level structures are frequently encountered in many real-world optimization problems. Decomposition techniques are a commonly applied approach used to handle nested multi-level structures; however, the typical problem-specific focus of such techniques has led to numerous specialized formulations and solution methods. This lack of generalized results for nested multi-level optimization problems is addressed in this … Read more
Motivated by applications in cloud computing, we study interval scheduling problems exhibiting economies of scale. An instance is given by a set of jobs, each with start time, end time, and a function representing the cost of scheduling a subset of jobs on the same machine. Specifically, we focus on the max-weight function and non-negative, … Read more
The Vehicle Allocation Problem (VAP) consists of repositioning empty vehicles across a set of terminals over a given planning horizon so as to maximize the profits generated from serving demand for transportation of goods between pair of terminals. This problem has been classically modeled using an extended space-time network which captures the staging of the … Read more
The Vehicle Allocation Problem (VAP) consists of allocating a fleet of vehicles to attend to the expected demand for freight transportation between terminals along a finite multiperiod planning horizon. The objective is to maximize the profits generated for the completed services. The previous deterministic and stochastic approaches used heuristic procedures and approximations for solving large-scale … Read more
By rerouting and retiming trains in real-time, the propagation of reactionary delay in complex station areas can be reduced. In this study, we propose a new optimisation model and solution algorithm that can be used to determine the best combination of route and schedule changes to make. Whilst several models have been proposed to tackle … Read more
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 7.0 of the SCIP Optimization Suite. The new version features the parallel presolving library PaPILO as a new addition to the suite. PaPILO 1.0 simplifies … Read more