The Arc-Item-Load and Related Formulations for the Cumulative Vehicle Routing Problem

The Capacitated Vehicle Routing Problem (CVRP) consists of finding the cheapest way to serve a set of customers with a fleet of vehicles of a given capacity. While serving a particular customer, each vehicle picks up its demand and carries its weight throughout the rest of its route. While costs in the classical CVRP are … Read more

Multi-Row Intersection Cuts based on the Infinity Norm

When generating multi-row intersection cuts for Mixed-Integer Linear Optimization problems, an important practical question is deciding which intersection cuts to use. Even when restricted to cuts that are facet-defining for the corner relaxation, the number of potential candidates is still very large, specially for instances of large size. In this paper, we introduce a subset … Read more

Split cuts from sparse disjunctions

Split cuts are arguably the most effective class of cutting planes within a branch-and-cut framework for solving general Mixed-Integer Programs (MIP). Sparsity, on the other hand, is a common characteristic of MIP problems, and it is an important part of why the simplex method works so well inside branch-and-cut. In this work, we evaluate the … Read more

Permutations in the factorization of simplex bases

The basis matrices corresponding to consecutive iterations of the simplex method only differ in a single column. This fact is commonly exploited in current LP solvers to avoid having to compute a new factorization of the basis at every iteration. Instead, a previous factorization is updated to reflect the modified column. Several methods are known … Read more

The (not so) Trivial Lifting in Two Dimensions

When generating cutting-planes for mixed-integer programs from multiple rows of the simplex tableau, the usual approach has been to relax the integrality of the non-basic variables, compute an intersection cut, then strengthen the cut coefficients corresponding to integral non-basic variables using the so-called trivial lifting procedure. Although of polynomial-time complexity in theory, this lifting procedure … Read more

Intersection Cuts for Single Row Corner Relaxations

We consider the problem of generating inequalities that are valid for one-row relaxations of a simplex tableau, with the integrality constraints preserved for one or more non-basic variables. These relaxations are interesting because they can be used to generate cutting planes for general mixed-integer problems. We first consider the case of a single non-basic integer … Read more

Numerically safe lower bounds for the Capacitated Vehicle Routing Problem

The resolution of integer programming problems is typically performed via branch-and-bound. Nodes of the branch-and-bound tree are pruned whenever the corresponding subproblem is proven not to contain a solution better than the best solution found so far. This is a key ingredient for achieving reasonable solution times. However, since subproblems are solved in floating-point arithmetic, … Read more

Exact Algorithms for the Chance-Constrained Vehicle Routing Problem

We study the chance-constrained vehicle routing problem (CCVRP), a version of the vehicle routing problem (VRP) with stochastic demands, where a limit is imposed on the probability that each vehicle’s capacity is exceeded. A distinguishing feature of our proposed methodologies is that they allow correlation between random demands, whereas nearly all existing exact methods for … Read more

A joint routing and speed optimization problem

Fuel cost contributes to a significant portion of operating cost in cargo transportation. Though classic routing models usually treat fuel cost as input data, fuel consumption heavily depends on the travel speed, which has led to the study of optimizing speeds over a given fixed route. In this paper, we propose a joint routing and … Read more

A disjunctive convex programming approach to the pollution routing problem

The pollution routing problem (PRP) aims to determine a set of routes and speed over each leg of the routes simultaneously to minimize the total operational and environmental costs. A common approach to solve the PRP exactly is through speed discretization, i.e., assuming that speed over each arc is chosen from a prescribed set of … Read more