Adam N. Letchford We consider a simple family of dynamic vehicle routing problems, in which we have a fixed fleet of identical vehicles, and customer requests arrive during the route-planning process. For this kind of problem, it is natural to use an insertion heuristic. We test several such heuristics computationally, on two different variants of the problem. It … Read more
The Simple Plant Location Problem (SPLP) is a well-known NP-hard optimisation problem with applications in logistics. Although many families of facet-defining inequalities are known for the associated polyhedron, very little work has been done on separation algorithms. We present the first ever polynomial-time separation algorithm for the SPLP that separates exactly over an exponentially large … Read more
In 2013, Buchheim and Wiegele introduced a quadratic optimisation problem, in which the domain of each variable is a closed subset of the reals. This problem includes several other important problems as special cases. We study some convex sets and polyhedra associated with the problem, and derive several families of strong valid inequalities. We also … Read more
We consider non-convex mixed-integer quadratic programs in which all variables are explicitly bounded. Many exact methods for such problems use additional variables, representing products of pairs of original variables. We study the convex hull of feasible solutions in this extended space. Some other approaches use bit representation to convert bounded integer variables into binary variables. … Read more
Some popular heuristics for combinatorial optimisation start by constructing a feasible solution to a dual of the problem. We show that such dual-based heuristics can exhibit highly counter-intuitive behaviour. In particular, for some problem classes, solving the dual exactly invariably leads to much worse primal solutions than solving the dual with a simple greedy heuristic. … Read more
The most effective software packages for solving mixed 0-1 linear programs use strong valid linear inequalities derived from polyhedral theory. We introduce a new procedure which enables one to take known valid inequalities for the knapsack polytope, and convert them into valid inequalities for the fixed-charge and single-node flow polytopes. The resulting inequalities are very … Read more
Lifted cover inequalities are well-known cutting planes for 0-1 linear programs. We show how one of the earliest lifting procedures, due to Balas, can be significantly improved. The resulting procedure has some unusual properties. For example, (i) it can yield facet-defining inequalities even if the given cover is not minimal, (ii) it can yield facet-defining … Read more
The stable set problem is a fundamental combinatorial optimisation problem, that is known to be very difficult in both theory and practice. Some of the solution algorithms in the literature are based on 0-1 linear programming formulations. We examine an entire family of such formulations, based on so-called clique and nodal inequalities. As well as … Read more
We present a new tool for generating cutting planes for NP-hard combinatorial optimisation problems. It is based on the concept of gadgets — small subproblems that are “glued” together to form hard problems — which we borrow from the literature on computational complexity. Using gadgets, we are able to derive huge (exponentially large) new families … Read more
Perspective functions have long been used to convert fractional programs into convex programs. More recently, they have been used to form tight relaxations of mixed-integer nonlinear programs with so-called indicator variables. Motivated by a practical application (maximising energy efficiency in an OFDMA system), we consider problems that have a fractional objective and indicator variables simultaneously. … Read more