We consider optimization problems with some binary variables, where the objective function is linear in these variables. The stability region of a given solution of such a problem is the polyhedral set of objective coefficients for which the solution is optimal. A priori knowledge of this set provides valuable information for sensitivity analysis and re-optimization … Read more
In this paper we present a cutting plane algorithm for the Set Covering problem. Cutting planes are generated by a “general” (i.e. not based on the “template paradigm”) separation algorithm based on the following idea: i) identify a suitably small subproblem defined by a subset of the constraints of the formulation; ii) run an exact … 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
The Generalized Assignment Problem is a well-known NP-hard combinatorial optimization problem which consists of minimizing the assignment costs a set of jobs to a set of machines satisfying capacity constraints. Most of the existing algorithms are based on Branch-and-Price, with lower bounds computed by Dantzig-Wolfe reformulation and column generation. In this paper we propose a … Read more
In this paper we address the following probabilistic version (PSC) of the set covering problem: min { cx | P (Ax>= xi) >= p, x_{j} in {0,1} j in N} where A is a 0-1 matrix, xi is a random 0-1 vector and p in (0,1] is the threshold probability level. In a recent development … Read more
The semi-Lagrangian Relaxation (SLR) method has been introduced in Beltran et al. (2006) to solve the p-median problem. In this paper we apply the method to the Uncapacitated Facility Location (UFL) problem. We perform computational experiments on two main collections of UFL problems with unknown optimal values. On one collection, we manage to solve to … Read more
In this paper we address the following probabilistic version (PSC) of the set covering problem: $min \{ cx \ |\ {\mathbb P} (Ax\ge \xi) \ge p,\ x_{j}\in \{0,1\}^N\}$ where $A$ is a 0-1 matrix, $\xi$ is a random 0-1 vector and $p\in (0,1]$ is the threshold probability level. We formulate (PSC) as a mixed integer … Read more
The topic of this paper are integer programming models in which a subset of 0/1-variables encode a partitioning of a set of objects into disjoint subsets. Such models can be surprisingly hard to solve by branch-and-cut algorithms if the permutation of the subsets of the partition is irrelevant. This kind of symmetry unnecessarily blows up … Read more
We introduce orbital branching, an effective branching method for integer programs containing a great deal of symmetry. The method is based on computing groups of variables that are equivalent with respect to the symmetry remaining in the problem after branching, including symmetry which is not present at the root node. These groups of equivalent variables, … Read more