the proceedings contain 34 papers. the topics discussed include: solving LP relaxations of large-scale precedence constrained problems;computing minimum multiway cuts in hypergraphs from hypertree packings;eigenvalue ...
ISBN:
(纸本)3642130356
the proceedings contain 34 papers. the topics discussed include: solving LP relaxations of large-scale precedence constrained problems;computing minimum multiway cuts in hypergraphs from hypertree packings;eigenvalue techniques for convex objective, nonconvex optimization problems;restricted b-matchings in degree-bounded graphs;zero-coefficient cuts;prize-collecting steiner network problems;on lifting integer variables in minimal inequalities;efficient edge splitting-off algorithms maintaining all-pairs edge-connectivities;on generalizations of network design problems with degree bounds;a polyhedral study of the mixed integer cut;symmetry matters for the sizes of extended formulations;a 3-approximation for facility location with uniform capacities;and approximability of 3- and 4-hop bounded disjoint paths problems.
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 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.
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 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 derive the first performance guarantees for a combinatorial online algorithm that schedules stochastic, nonpreemptive jobs on unrelated machines to minimize the expectation of the total weighted completion time. Pr...
详细信息
ISBN:
(数字)9783319592503
ISBN:
(纸本)9783319592503;9783319592497
We derive the first performance guarantees for a combinatorial online algorithm that schedules stochastic, nonpreemptive jobs on unrelated machines to minimize the expectation of the total weighted completion time. Prior work on unrelated machine scheduling with stochastic jobs was restricted to the offline case, and required sophisticated linear or convex programming relaxations for the assignment of jobs to machines. Our algorithm is purely combinatorial, and therefore it also works for the online setting. As to the techniques applied, this paper shows how the dual fitting technique can be put to work for stochastic and nonpreemptive scheduling problems.
A clutter is identically self-blocking if it is equal to its blocker. We prove that every identically self-blocking clutter different from {{a}} is nonideal. Our proofs borrow tools from Gauge Duality and Quadratic Pr...
详细信息
ISBN:
(数字)9783030179533
ISBN:
(纸本)9783030179533;9783030179526
A clutter is identically self-blocking if it is equal to its blocker. We prove that every identically self-blocking clutter different from {{a}} is nonideal. Our proofs borrow tools from Gauge Duality and Quadratic programming. Along the way we provide a new lower bound for the packing number of an arbitrary clutter.
Software for mixed-integer linear programming can return incorrect results for a number of reasons, one being the use of inexact floating-point arithmetic. Even solvers that employ exact arithmetic may suffer from pro...
详细信息
ISBN:
(数字)9783319592503
ISBN:
(纸本)9783319592503;9783319592497
Software for mixed-integer linear programming can return incorrect results for a number of reasons, one being the use of inexact floating-point arithmetic. Even solvers that employ exact arithmetic may suffer from programming or algorithmic errors, motivating the desire for a way to produce independently verifiable certificates of claimed results. Due to the complex nature of state-of-the-art MIP solution algorithms, the ideal form of such a certificate is not entirely clear. this paper proposes such a certificate format designed with simplicity in mind, which is composed of a list of statements that can be sequentially verified using a limited number of inference rules. We present a supplementary verification tool for compressing and checking these certificates independently of how they were created. We report computational results on a selection of MIP instances from the literature. To this end, we have extended the exact rational version of the MIP solver SCIP to produce such certificates.
Given a factorable function f, we propose a procedure that constructs a concave underestimator of f that is tight at a given point. these underestimators can be used to generate intersection cuts. A peculiarity of the...
详细信息
ISBN:
(纸本)9783030179533;9783030179526
Given a factorable function f, we propose a procedure that constructs a concave underestimator of f that is tight at a given point. these underestimators can be used to generate intersection cuts. A peculiarity of these underestimators is that they do not rely on a bounded domain. We propose a strengthening procedure for the intersection cuts that exploits the bounds of the domain. Finally, we propose an extension of monoidal strengthening to take advantage of the integrality of the non-basic variables.
暂无评论