the proceedings contain 33 papers. the topics discussed include: on the structure of reduced kernel lattice bases;all-or-nothing generalized assignment with application to scheduling advertising campaigns;intersection...
ISBN:
(纸本)9783642366932
the proceedings contain 33 papers. the topics discussed include: on the structure of reduced kernel lattice bases;all-or-nothing generalized assignment with application to scheduling advertising campaigns;intersection cuts for mixed integer conic quadratic sets;content placement via the exponential potential function method;a complexity and approximability study of the bilevel knapsack problem;matroid and knapsack center problems;cut-generating functions;on some generalizations of the split closure;packing interdiction and partial covering problems;on valid inequalities for quadratic programming with continuous variables and binary indicators;single commodity-flow algorithms for lifts of graphic and co-graphic matroids;a stochastic probing problem with applications;thrifty algorithms for multistage robust optimization;and two dimensional optimal mechanism design for a sequencing problem.
this book constitutes the proceedings of the 16th International conference 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 16th International conference 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.
Split cuts form a well-known class of valid inequalities for mixed-integerprogramming problems (MIP). Cook et al. (1990) showed that the split closure of a rational polyhedron P is again a polyhedron. In this paper, ...
详细信息
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.
Balas introduced intersection cuts for mixed integer linear sets. Intersection cuts are given by closed form formulas and form an important class of cuts for solving mixed integer linear programs. In this paper we int...
详细信息
Consider a binary matroid M given by its matrix representation. We show that if M is a lift of a graphic or a co-graphic matroid, then in polynomial time we can either solve the single commodity flow problem for M or ...
详细信息
Let Lm be the Lorentz cone in m. Given A ∈ mxn1, and B ∈ mxn2 and b ∈ m, a simple second order conic mixed-integer set (SOCMIS) is a set of the form {(x, y) ∈ n1 x n2 | Ax + By - b ∈ Lm}. We show that there exist...
详细信息
For a convex set S, we study the facial structure of its integer hull, S. Crucial to our study is the decomposition of the integer hull into the convex hull of its extreme points, conv(ext(S)), and its recession cone....
详细信息
We start with definitions given by Plotkin, Shmoys, and Tardos [16]. Given A∈?m×n, b∈?m and a polytope P $
 \subseteq$
 \subseteq ? n , the fractional packing problem is to find an x ∈ P such t...
ISBN:
(纸本)3540660194
We start with definitions given by Plotkin, Shmoys, and Tardos [16]. Given A∈?m×n, b∈?m and a polytope P $
\subseteq$
\subseteq ? n , the fractional packing problem is to find an x ∈ P such that Ax ≤ b if such an x exists. An ∈-approximate solution to this problem is an x ∈ P such that Ax ≤ (1+∈)b. An ∈-relaxed decision procedure always finds an ∈-approximate solution if an exact solution exists.
In optimization problems such as integer programs or their relaxations, one encounters feasible regions of the form {x ∈ +n : Rx ∈ S} where R is a general real matrix and S ⊂ q is a specific closed set with 0 ∉ S. F...
详细信息
暂无评论