Adam N. Letchford Non-Convex Quadratic Programming with Box Constraints is a fundamental NP-hard global optimisation problem. Recently, some authors have studied a certain family of convex sets associated with this problem. We prove several fundamental results concerned with these convex sets: we determine their dimension, characterise their extreme points and vertices, show their invariance under certain affine transformations, … Read more
The Single Row Facility Layout Problem (SRFLP) is the problem of arranging facilities of given lengths on a line, while minimizing a weighted sum of the distances between all pairs of facilities. The SRFLP is strongly NP-hard and includes the well-known linear arrangement problem as a special case. We perform the first ever polyhedral study … Read more
Valid inequalities for 0-1 knapsack polytopes often prove useful when tackling hard 0-1 Linear Programming problems. To use such inequalities effectively, one needs separation algorithms for them, i.e., routines for detecting when they are violated. We show that the separation problems for the so-called extended cover and weight inequalities can be solved exactly in O(nb) … Read more
The Quadratic Knapsack Problem can be formulated, using an idea of Glover, as a mixed 0-1 linear program with only 2n variables. We present a simple method for strengthening that formulation, which gives good results when the profit matrix is dense and non-negative. CitationWorking Paper, Department of Management Science, Lancaster University, May 2007.ArticleDownload View PDF