the Generate-and-Solve is a hybrid framework to cope with hard combinatorialoptimization problems by artificially reducing the search space of solutions. In this framework, a metaheuristic engine works as a generator...
详细信息
ISBN:
(纸本)9783642371981
the Generate-and-Solve is a hybrid framework to cope with hard combinatorialoptimization problems by artificially reducing the search space of solutions. In this framework, a metaheuristic engine works as a generator of reduced instances of the problem. these instances, in turn, can be more easily handled by an exact solver to provide a feasible (optimal) solution to the original problem. this approach has commonly employed genetic algorithms and it has been particularly effective in dealing with cutting and packing problems. In this paper, we present an instantiation of the framework for tackling the constrained two-dimensional non-guillotine cutting problem and the container loading problem using a simulated annealing generator. We conducted computational experiments on a set of difficult benchmark instances. Results show that the simulated annealing implementation overachieves previous versions of the Generate-and-Solve framework. In addition, the framework is shown to be competitive with current state-of-the-art approaches to solve the problems studied here.
this note considers convex optimization problems over base polytopes of polymatroids. We show that the decomposition algorithm for the separable convex function minimization problems helps us give simple sufficient co...
详细信息
ISBN:
(纸本)9783540727910
this note considers convex optimization problems over base polytopes of polymatroids. We show that the decomposition algorithm for the separable convex function minimization problems helps us give simple sufficient conditions for the rationality of optimal solutions and that it leads us to some interesting properties, including the equivalence of the lexicographically optimal base problem, introduced by Fujishige, and the submodular utility allocation market problem, introduced by Jain and Vazirani. In addition, we develop an efficient implementation of the decomposition algorithm via parametric submodular function minimization algorithms. Moreover, we show that, in some remarkable cases, non-separable convex optimization problems over base polytopes can be solved in strongly polynomial time.
We study the mixed-integer rounding (MIR) closure of polyhedra. the MIR closure of a polyhedron is equal to its split closure and the associated separation problem is NP-hard. We describe a mixed-integerprogramming (...
详细信息
ISBN:
(纸本)9783540727910
We study the mixed-integer rounding (MIR) closure of polyhedra. the MIR closure of a polyhedron is equal to its split closure and the associated separation problem is NP-hard. We describe a mixed-integerprogramming (MIP) model with linear constraints and a nonlinear objective for separating an arbitrary point from the MIR closure of a given mixed-integer set. We linearize the objective using additional variables to produce a linear MIP model that solves the separation problem approximately, with an accuracy that depends on the number of additional variables used. Our analysis yields a short proof of the result of Cook, Karman and Schrijver (1990) that the split closure of a polyhedron is again a polyhedron. We also present some computational results with our approximate separation model.
In this paper we use facets of the convex hull of mixed-integer sets with two and three variables to derive valid inequalities for integer sets defined by a single equation. these inequalities also define facets of th...
详细信息
ISBN:
(纸本)3540221131
In this paper we use facets of the convex hull of mixed-integer sets with two and three variables to derive valid inequalities for integer sets defined by a single equation. these inequalities also define facets of the master cyclic group polyhedron of Gomory. In particular, our inequalities generalize the 2slope facets of Araoz, Gomory, Johnson and Evans (2003). In addition, they dominate the strong fractional cuts of Letchford and Lodi (2002).
this book constitutes the proceedings of the 16thinternationalconference on integerprogramming and combinatorialoptimization, IPCO 2013, held in Valparaíso, Chile, in March 2013. the 33 full papers presented ...
详细信息
ISBN:
(数字)9783642366949
ISBN:
(纸本)9783642366932
this book constitutes the proceedings of the 16thinternationalconference on integerprogramming and combinatorialoptimization, IPCO 2013, held in Valparaíso, Chile, in March 2013. the 33 full papers presented were carefully reviewed and selected from 98 submissions. the conference is a forum for researchers and practitioners working on various aspects of integerprogramming and combinatorialoptimization withthe aim to present recent developments in theory, computation, and applications. the scope of IPCO is viewed in a broad sense, to include algorithmic and structural results in integerprogramming and combinatorialoptimization as well as revealing computational studies and novel applications of discrete optimization to practical problems.
this paper contributes to the theory of cutting planes for mixed integer linear programs (MILPs). Minimal valid inequalities are well understood for a relaxation of an MILP in tableau form where all the nonbasic varia...
详细信息
ISBN:
(纸本)9783642130359
this paper contributes to the theory of cutting planes for mixed integer linear programs (MILPs). Minimal valid inequalities are well understood for a relaxation of an MILP in tableau form where all the nonbasic variables are continuous. In this paper we study lifting functions for the nonbasic integer variables starting from such minimal valid inequalities. We characterize precisely when the lifted coefficient is equal to the coefficient of the corresponding continuous variable in every minimal lifting. the answer is a nonconvex region that can be obtained as the union of convex polyhedra.
We consider the s-t-path TSP: given a finite metric space with two elements s and t, we look for a path from s to t that contains all the elements and has minimum total distance. We improve the approximation ratio for...
详细信息
ISBN:
(数字)9783319334615
ISBN:
(纸本)9783319334615;9783319334608
We consider the s-t-path TSP: given a finite metric space with two elements s and t, we look for a path from s to t that contains all the elements and has minimum total distance. We improve the approximation ratio for this problem from 1.599 to 1.566. Like previous algorithms, we solve the natural LP relaxation and represent an optimum solution x* as a convex combination of spanning trees. Gao showed that there exists a spanning tree in the support of x* that has only one edge in each narrow cut (i.e., each cut C with x*(C) < 2). Our main theorem says that the spanning trees in the convex combination can be chosen such that many of them are such "Gao trees" simultaneously at all sufficiently narrow cuts.
We study the problem of optimizing over the set of all combinatorial embeddings of a given planar graph. Our objective function prefers certain cycles of G as face cycles in the embedding. the motivation for studying ...
详细信息
ISBN:
(纸本)3540660194
We study the problem of optimizing over the set of all combinatorial embeddings of a given planar graph. Our objective function prefers certain cycles of G as face cycles in the embedding. the motivation for studying this problem arises in graph drawing, where the chosen embedding has an important influence on the aesthetics of the drawing. We characterize the set of all possible embeddings of a given biconnected planar graph G by means of a system of linear inequalities with {0, 1}-variables corresponding to the set of those cycles in G which can appear in a combinatorial embedding. this system of linear inequalities can be constructed recursively using SPQR-trees and a new splitting operation. Our computational results on two benchmark sets of graphs are surprising: the number of variables and constraints seems to grow only linearly withthe size of the graphs although the number of embeddings grows exponentially. For all tested graphs (up to 500 vertices) and linear objective functions, the resulting integer linear programs could be generated within 10 minutes and solved within two seconds on a Sun Enterprise 10000 using CPLEX.
Gomory-Chvatal cuts are prominent in integerprogramming. the Gomory-Chvatal closure of a polyhedron is the intersection of all half spaces defined by its Gomory-Chvatal cuts. In this paper, we show that it is NP-comp...
详细信息
ISBN:
(纸本)9783319334615;9783319334608
Gomory-Chvatal cuts are prominent in integerprogramming. the Gomory-Chvatal closure of a polyhedron is the intersection of all half spaces defined by its Gomory-Chvatal cuts. In this paper, we show that it is NP-complete to decide whether the Gomory-Chvatal closure of a rational polyhedron is empty, even when this polyhedron contains no integer point. this implies that the problem of deciding whether the Gomory-Chvatal closure of a rational polyhedron P is identical to the integer hull of P is NP-hard. Similar results are also proved for the {-1, 0, 1}-cuts and {0, 1}-cuts, two special types of Gomory-Chvatal cuts with coefficients restricted in {-1, 0, 1} and {0, 1}, respectively.
We introduce a method for proving Sum-of-Squares (SoS)/Lasserre hierarchy lower bounds when the initial problem formulation exhibits a high degree of symmetry. Our main technical theorem allows us to reduce the study ...
详细信息
ISBN:
(纸本)9783319334615;9783319334608
We introduce a method for proving Sum-of-Squares (SoS)/Lasserre hierarchy lower bounds when the initial problem formulation exhibits a high degree of symmetry. Our main technical theorem allows us to reduce the study of the positive semidefiniteness to the analysis of "well-behaved" univariate polynomial inequalities. We illustrate the technique on two problems, one unconstrained and the other with constraints. More precisely, we give a short elementary proof of Grigoriev/Laurent lower bound for finding the integer cut polytope of the complete graph. We also show that the SoS hierarchy requires a non-constant number of rounds to improve the initial integrality gap of 2 for the Min-Knapsack linear program strengthened with cover inequalities.
暂无评论