Search

A New Family of Valid-Inequalities for Dantzig-Wolfe Reformulation of Mixed Integer Linear Programs In "Consistency Cuts for Dantzig-Wolfe Reformulation," Jens Vinther Clausen, Richard Lusby, and Stefan Ropke present a new family of valid inequalities to be applied to Dantzig-Wolfe reformulations with binary linking variables. They show that, for Dantzig-Wolfe reformulations of mixed integer linear programs that satisfy certain properties, it is enough to solve the linear programming relaxation of the Dantzig-Wolfe reformulation with all consistency cuts to obtain integer solutions. An example of this is the temporal knapsack problem; the effectiveness of the cuts is tested on a set of 200 instances of this problem, and the results are state-of-the-art solution times. For problems that do not satisfy these conditions, the cuts can still be used in a branch-and-cut-and-price framework. In order to show this, the cuts are applied to a set of generic mixed linear integer programs from the online library MIPLIB. These tests show the applicability of the cuts in general. This paper introduces a family of valid inequalities, which we term consistency cuts, to be applied to a Dantzig-Wolfe reformulation (or decomposition) with linking variables. We prove that these cuts ensure an integer solution to the corresponding Dantzig-Wolfe relaxation when certain criteria to the structure of the decomposition are met. We implement the cuts and use them to solve a commonly used test set of 200 instances of the temporal knapsack problem. We assess the performance with and without the cuts and compare further to CPLEX and other solution methods that have historically been used to solve the test set. By separating consistency cuts, we show that we can obtain optimal integer solutions much faster than the other methods and even solve the remaining unsolved problems in the test set. We also perform a second test on instances from the MIPLIB 2017 online library of mixed-integer programs, showing the potential of the cuts on a wider range of problems. [ABSTRACT FROM AUTHOR]

This paper presents a branch-and-price algorithm for the time-dependent vehicle routing problem with time windows (TDVRPTW).We capture road congestion by considering time-dependent travel times, i.e., depending on the departure time to a customer, a different travel time is incurred. We consider the variant of the TDVRPTW where the objective is to minimize total route duration and denote this variant the duration minimizing TDVRPTW (DM-TDVRPTW). Because of time dependency, vehicles' dispatch times at the depot are crucial as road congestion might be avoided. Because of its complexity, all known solution methods to the DM-TDVRPTW are based on (meta-)heuristics. The decomposition of an arc-based formulation leads to a set-partitioning problem as the master problem, and a time-dependent shortest path problem with resource constraints as the pricing problem. The master problem is solved by means of column generation, and a tailored labeling algorithm is used to solve the pricing problem. We introduce new dominance criteria that allow more label dominance. For our numerical results, we modified Solomon's data sets by adding time dependency. Our algorithm is able to solve about 63% of the instances with 25 customers, 38% of the instances with 50 customers, and 15% of the instances with 100 customers. [ABSTRACT FROM AUTHOR]

This paper presents an exact method for solving the symmetric two-echelon capacitated vehicle routing problem, a transportation problem concerned with the distribution of goods from a depot to a set of customers through a set of satellite locations. The presented method is based on an edge flow model that is a relaxation and provides a valid lower bound. A specialized branching scheme is employed to obtain feasible solutions. Out of a test set of 93 instances the algorithm is able to solve 47 to optimality, surpassing previous exact algorithms. [ABSTRACT FROM AUTHOR]

In the pickup and delivery problem with time windows vehicle routes must be designed to satisfy a set of transportation requests, each involving a pickup and delivery location, under capacity, time window, and precedence constraints. This paper introduces a new branch-and-cut-and-price algorithm in which lower bounds are computed by solving through column generation the linear programming relaxation of a set partitioning formulation. Two pricing subproblems are considered in the column generation algorithm: an elementary and nonelementary shortest path problem. Valid inequalities are added dynamically to strengthen the relaxations. Some of the previously proposed inequalities for the pickup and delivery problem with time windows are also shown to be implied by the set partitioning formulation. Computational experiments indicate that the proposed algorithm outperforms a recent branch-and-cut algorithm. [ABSTRACT FROM AUTHOR]