1,721,089 research outputs found
A compact variant of the QCR method for quadratically constrained quadratic 0-1 programs
Full text linkQuadratic Convex Reformulation (QCR) is a technique that was originally proposed for quadratic 0-1 programs, and then extended to various other problems. It is used to convert non-convex instances into convex ones, in such a way that the bound obtained by solving the continuous relaxation of the reformulated instance is as strong as possible. In this paper, we focus on the case of quadratically constrained quadratic 0-1 programs. The variant of QCR previously proposed for this case involves the addition of a quadratic number of auxiliary continuous variables. We show that, in fact, at most one additional variable is needed. Some computational results are also presented
Separation algorithms for 0-1 knapsack polytopes
No full textValid inequalities for 0-1 knapsack polytopes often prove useful
when tackling hard 0-1 Linear Programming problems. To generate
such inequalities, one needs separation algorithms for them, i.e., rou-
tines for detecting when they are violated. We present new exact
and heuristic separation algorithms for several classes of inequalities,
namely lifted cover, extended cover, weight and lifted pack inequalities.
Moreover, we show how to improve a recent separation algorithm for
the 0-1 knapsack polytope itself. Extensive computational results, on
MIPLIB and OR Library instances, show the strengths and limitations
of the inequalities and algorithms considered
A binarisation heuristic for non-convex quadratic programming with box constraints
Full text linkNon-convex quadratic programming with box constraints is a fundamental problem in the global optimisation 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 optimisation. Some very encouraging computational results are given
On the Lovász theta function and some variants
Full text linkThe Lovász 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 Lovász and the other to Gr�ötschel et al. The former SDP is often thought to be preferable computationally, since it has fewer variables and constraints. We derive some new results on these two equivalent SDPs. The surprising result is that, if we weaken the SDPs by aggregating constraints, or strengthen them by adding cutting planes, the equivalence breaks down. In particular, the Gr�ötschel et al. scheme typically yields a stronger bound than the Lovász one
Local and global lifted cover inequalities for the 0-1 multidimensional knapsack problem
Full text linkThe 0-1 Multidimensional Knapsack Problem (0-1 MKP) is a well-
known (and strongly N P -hard) combinatorial optimization problem
with many applications. Up to now, the ma jority of upper bounding
techniques for the 0-1 MKP have been based on Lagrangian or surro-
gate relaxation. We show that good upper bounds can be obtained by
a cutting plane method based on lifted cover inequalities (LCIs). As
well as using traditional LCIs, we use some new ‘global’ LCIs, which
take the whole constraint matrix into account
Complexity results for the gap inequalities for the max-cut problem
Full text linkWe prove several complexity results about the gap inequalities for the max-cut problem, including (i) the gap-1 inequalities do not imply the other gap inequalities, unless NP=Co NP; (ii) there must exist non-redundant gap inequalities with exponentially large coefficients, unless NP=Co NP; (iii) the associated separation problem can be solved in finite (doubly exponential) time
Matheuristics : survey and synthesis
Full text linkIn integer programming and combinatorial optimisation, people use the term matheuristics to refer to methods that are heuristic in nature, but draw on concepts from the literature on exact methods. We survey the literature on this topic, with a particular emphasis on matheuristics that yield both primal and dual bounds (i.e., upper and lower bounds in the case of a minimisation problem). We also make some comments about possible future developments
Good triangulations yield good tours
Full text linkConsider the following heuristic for planar Euclidean instances of the traveling salesman problem (TSP): select a subset of the edges which induces a planar graph, and solve either the TSP or its graphical relaxation on that graph. In this paper, we give several motivations for considering this heuristic, along with extensive computational results. It turns out that the Delaunay and greedy triangulations make effective choices for the induced planar graph. Indeed, our experiments show that the resulting tours are on average within 0.1% of optimality.Scope and purposeThe traveling salesman problem (TSP) is a fundamental and well-known problem in combinatorial optimisation. It has many applications, for example in vehicle routing and machine scheduling. This paper proposes several heuristics methods for the Euclidean TSP, based on the use of triangulations, and gives extensive computational results
Small bipartite subgraph polytopes
Full text linkWe compute a complete linear description of the bipartite subgraph polytope, for up to seven nodes, and a conjectured complete description for eight nodes. We then show how these descriptions were used to compute the integrality ratio of various relaxations of the max-cut problem, again for up to eight nodes
Gap inequalities for the max-cut problem: a cutting-plane algorithm
No full textLaurent & Poljak introduced a class of valid inequalities for the max-cut problem, called gap inequalities, which include many other known inequalities as special cases. The gap inequalities have received little attention and are poorly understood. This paper presents the first ever computational results. In particular, we describe a cutting-plane scheme based on an effective heuristic separation algorithm for gap inequalities, and show that these yield extremely strong upper bounds in practice
- …
