An Exact Algorithm for a Resource Allocation Problem in Mobile Wireless Communications

We consider a challenging resource allocation problem arising in mobile wireless communications. The goal is to allocate the available channels and power in a so-called OFDMA system, in order to maximise the transmission rate, subject to quality of service (QoS) constraints. Standard MINLP software struggled to solve even small instances of this problem. Using outer … Read more

Projection Results for the k-Partition Problem

The k-partition problem is an NP-hard combinatorial optimisation problem with many applications. Chopra and Rao introduced two integer programming formulations of this problem, one having both node and edge variables, and the other having only edge variables. We show that, if we take the polytopes associated with the `edge-only’ formulation, and project them into a … Read more

On the Lovasz Theta Function and Some Variants

The Lovasz theta function of a graph is a well-known upper bound on the stability number. It can be computed efficiently by solving a semidefinite program (SDP). Actually, one can solve either of two SDPs, one due to Lovasz and the other to Groetschel et al. The former SDP is often thought to be preferable … Read more

New Valid Inequalities and Facets for the Simple Plant Location Problem

The Simple Plant Location Problem is a well-known (and NP-hard) combinatorial optimisation problem, with applications in logistics. We present a new family of valid inequalities for the associated family of polyhedra, and show that it contains an exponentially large number of new facet-defining members. We also present a new procedure, called facility augmentation, which enables … Read more

Stronger Multi-Commodity Flow Formulations of the (Capacitated) Sequential Ordering Problem

The “sequential ordering problem” (SOP) is the generalisation of the asymmetric travelling salesman problem in which there are precedence relations between pairs of nodes. Hernández & Salazar introduced a “multi-commodity flow” (MCF) formulation for a generalisation of the SOP in which the vehicle has a limited capacity. We strengthen this MCF formulation by fixing variables … Read more

A Binarisation Heuristic for Non-Convex Quadratic Programming with Box Constraints

Non-convex quadratic programming with box constraints is a fundamental problem in the global optimization literature, being one of the simplest NP-hard nonlinear programs. We present a new heuristic for this problem, which enables one to obtain solutions of excellent quality in reasonable computing times. The heuristic consists of four phases: binarisation, convexification, branch-and-bound, and local … Read more

Stronger Multi-Commodity Flow Formulations of the Capacitated Vehicle Routing Problem

The Capacitated Vehicle Routing Problem is a much-studied (and strongly NP-hard) combinatorial optimization problem, for which many integer programming formulations have been proposed. We present some new multi-commodity flow (MCF) formulations, and show that they dominate all of the existing ones, in the sense that their continuous relaxations yield stronger lower bounds. Moreover, we show … Read more

A Cut-and-Branch Algorithm for the Quadratic Knapsack Problem

The Quadratic Knapsack Problem (QKP) is a well-known NP-hard combinatorial optimisation problem, with many practical applications. We present a ‘cut-and-branch’ algorithm for the QKP, in which a cutting-plane phase is followed by a branch-and-bound phase. The cutting-plane phase is more sophisticated than the existing ones in the literature, incorporating several classes of cutting planes, two … Read more

Cutting Planes for RLT Relaxations of Mixed 0-1 Polynomial Programs

The Reformulation-Linearization Technique (RLT), due to Sherali and Adams, can be used to construct hierarchies of linear programming relaxations of mixed 0-1 polynomial programs. As one moves up the hierarchy, the relaxations grow stronger, but the number of variables increases exponentially. We present a procedure that generates cutting planes at any given level of the … Read more

A Dynamic Programming Heuristic for the Quadratic Knapsack Problem

It is well known that the standard (linear) knapsack problem can be solved exactly by dynamic programming in O(nc) time, where n is the number of items and c is the capacity of the knapsack. The quadratic knapsack problem, on the other hand, is NP-hard in the strong sense, which makes it unlikely that it … Read more