We obtain optimal lower and upper bounds for the (additive) integrality gaps of integer knapsack problems. In a randomised setting, we show that the integrality gap of a "typical" knapsack problem is drastic...
详细信息
ISBN:
(数字)9783319592503
ISBN:
(纸本)9783319592503;9783319592497
We obtain optimal lower and upper bounds for the (additive) integrality gaps of integer knapsack problems. In a randomised setting, we show that the integrality gap of a "typical" knapsack problem is drastically smaller than the integrality gap that occurs in a worst case scenario.
We describe an algorithm that finds an is an element of-approximate solution to a concave mixed-integer quadratic programming problem. the running time of the proposed algorithm is polynomial in the size of the proble...
详细信息
ISBN:
(数字)9783319334615
ISBN:
(纸本)9783319334615;9783319334608
We describe an algorithm that finds an is an element of-approximate solution to a concave mixed-integer quadratic programming problem. the running time of the proposed algorithm is polynomial in the size of the problem and in 1/is an element of, provided that the number of integer variables and the number of negative eigenvalues of the objective function are fixed. the running time of the proposed algorithm is expected unless P = NP.
We extend the Barvinok-Woods algorithm for enumeration of integer points in projections of polytopes to unbounded polyhedra. To achieve this, we employ a new structural result on projections of semilinear subsets of t...
详细信息
ISBN:
(纸本)9783319592503;9783319592497
We extend the Barvinok-Woods algorithm for enumeration of integer points in projections of polytopes to unbounded polyhedra. To achieve this, we employ a new structural result on projections of semilinear subsets of the integer lattice.
We introduce a concept that generalizes several different notions of a "centerpoint" in the literature. We develop an oracle-based algorithm for convex mixed-integeroptimization based on centerpoints. Furth...
详细信息
ISBN:
(数字)9783319334615
ISBN:
(纸本)9783319334615;9783319334608
We introduce a concept that generalizes several different notions of a "centerpoint" in the literature. We develop an oracle-based algorithm for convex mixed-integeroptimization based on centerpoints. Further, we show that algorithms based on centerpoints are "best possible" in a certain sense. Motivated by this, we establish several structural results about this concept and provide efficient algorithms for computing these points.
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 consider a new semidefinite programming (SDP) relaxation of the symmetric traveling salesman problem (TSP) that may be obtained via an SDP relaxation of the more general quadratic assignment problem (QAP). We show ...
详细信息
We consider a new semidefinite programming (SDP) relaxation of the symmetric traveling salesman problem (TSP) that may be obtained via an SDP relaxation of the more general quadratic assignment problem (QAP). We show that the new relaxation dominates the one in [D. Cvetkovic, M. Cangalovic, and V. Kovacevic-Vujcic, Semidefinite programming methods for the symmetric traveling salesman problem, in Proceedings of the 7thinternationalipcoconference on integerprogramming and combinatorialoptimization, Springer-Verlag, London, UK, 1999, pp. 126-136]. Unlike the bound of Cvetkovic et al., the new SDP bound is not dominated by the Held-Karp linear programming bound, or vice versa.
the infinite models in integerprogramming can be described as the convex hull of some points or as the intersection of halfspaces derived from valid functions. In this paper we study the relationships between these t...
详细信息
ISBN:
(数字)9783319592503
ISBN:
(纸本)9783319592503;9783319592497
the infinite models in integerprogramming can be described as the convex hull of some points or as the intersection of halfspaces derived from valid functions. In this paper we study the relationships between these two descriptions. Our results have implications for finite dimensional corner polyhedra. One consequence is that nonnegative continuous functions suffice to describe finite dimensional corner polyhedra with rational data. We also discover new facts about corner polyhedra with non-rational data.
We consider the question of which nonconvex sets can be represented exactly as the feasible sets of mixed-integer convex optimization problems. We state the first complete characterization for the case when the number...
详细信息
ISBN:
(纸本)9783319592503;9783319592497
We consider the question of which nonconvex sets can be represented exactly as the feasible sets of mixed-integer convex optimization problems. We state the first complete characterization for the case when the number of possible integer assignments is finite. We develop a characterization for the more general case of unbounded integer variables together with a simple necessary condition for representability which we use to prove the first known negative results. Finally, we study representability of subsets of the natural numbers, developing insight towards a more complete understanding of what modeling power can be gained by using convex sets instead of polyhedral sets;the latter case has been completely characterized in the context of mixed-integer linear optimization.
We consider linear relaxations for multilinear optimization problems. In a recent paper, Khajavirad proved that the extended flower relaxation is at least as strong as the relaxation of any recursive McCormick lineari...
详细信息
ISBN:
(纸本)9783031598340;9783031598357
We consider linear relaxations for multilinear optimization problems. In a recent paper, Khajavirad proved that the extended flower relaxation is at least as strong as the relaxation of any recursive McCormick linearization (Operations Research Letters 51 (2023) 146-152). In this paper we extend the result to more general linearizations, and present a simpler proof. Moreover, we complement Khajavirad's result by showing that the intersection of the relaxations of such linearizations and the extended flower relaxation are equally strong.
Robust combinatorialoptimization with budget uncertainty is one of the most popular approaches for integrating uncertainty in optimization problems. the existence of a compact reformulation for (mixed-integer) linear...
详细信息
ISBN:
(数字)9783031327261
ISBN:
(纸本)9783031327254;9783031327261
Robust combinatorialoptimization with budget uncertainty is one of the most popular approaches for integrating uncertainty in optimization problems. the existence of a compact reformulation for (mixed-integer) linear programs and positive complexity results give the impression that these problems are relatively easy to solve. However, the practical performance of the reformulation is actually quite poor when solving robust integer problems due to its weak linear relaxation. To overcome the problems arising from the weak formulation, we propose a procedure to derive new classes of valid inequalities for robust binary optimization problems. For this, we recycle valid inequalities of the underlying deterministic problem such that the additional variables from the robust formulation are incorporated. the valid inequalities to be recycled may either be readily available model constraints or actual cutting planes, where we can benefit from decades of research on valid inequalities for classical optimization problems. We first demonstrate the strength of the inequalities theoretically, by proving that recycling yields a facet-defining inequality in surprisingly many cases, even if the original valid inequality was not facet-defining. Afterwards, we show in a computational study that using recycled inequalities leads to a significant improvement of the computation time when solving robust optimization problems.
暂无评论