the proceedings contain 34 papers. the topics discussed include: a strongly polynomial time algorithm for multicriteria global minimum cuts;integer programs with prescribed number of solutions and a weighted version o...
ISBN:
(纸本)9783319075563
the proceedings contain 34 papers. the topics discussed include: a strongly polynomial time algorithm for multicriteria global minimum cuts;integer programs with prescribed number of solutions and a weighted version of Doignon-Bell-Scarf's theorem;sequence independent, simultaneous and multidimensional lifting of generalized flow covers for the semi-continuous knapsack problem with generalized upper bounds constraints;maximum weighted induced bipartite subgraphs and acyclic subgraphs of planar cubic graphs;n-step cycle inequalities: facets for continuous n-mixing set and strong cuts for multi-module capacitated lot-sizing problem;the triangle splitting method for biobjective mixed integerprogramming;box-constrained mixed-integer polynomial optimization using separable underestimators;the all-or-nothing flow problem in directed graphs with symmetric demand pairs;and strong LP formulations for scheduling splittable jobs on unrelated machines.
this book constitutes the refereed proceedings of the 17th international conference on integer programming and combinatorial optimization, ipco 2014, held in Bonn, Germany, in June 2014. the 34 full papers presented w...
详细信息
ISBN:
(数字)9783319075570
ISBN:
(纸本)9783319075563
this book constitutes the refereed proceedings of the 17th international conference on integer programming and combinatorial optimization, ipco 2014, held in Bonn, Germany, in June 2014. the 34 full papers presented were carefully reviewed and selected from 143 submissions. the conference is a forum for researchers and practitioners working on various aspects of integerprogramming and combinatorialoptimization. the aim is to present recent developments in theory, computation, and applications in these areas. 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.
We present the first criterion space search algorithm, the triangle splitting method, for finding the efficient frontier of a biobjective mixed integer program. the algorithm is relatively easy to implement and conver...
详细信息
For a given set X ⊆ Z d of integer points, we investigate the smallest number of facets of any polyhedron whose set of integer points is conv(X) ∩ Z d . this quantity, which we call the relaxation complexity of X, co...
详细信息
In this paper we consider a variant of the betweenness problem occurring in computational biology. We present a new polyhedral approach which incorporates the solution of consecutive ones problems and show that it sup...
详细信息
ISBN:
(纸本)354064590X
In this paper we consider a variant of the betweenness problem occurring in computational biology. We present a new polyhedral approach which incorporates the solution of consecutive ones problems and show that it supersedes an earlier one. A particular feature of this new branch-and-cut algorithm is that it is not based on an explicit integerprogramming formulation of the problem and makes use of automatically generated facet-defining inequalities.
We introduce the simple extension complexity of a polytope P as the smallest number of facets of any simple (i.e., non-degenerate in the sense of linear programming) polytope which can be projected onto P. We devise a...
详细信息
A binary clutter is cycling if its packing and covering linear program have integral optimal solutions for all eulerian edge capacities. We prove that the clutter of odd st-walks of a signed graph is cycling if and on...
详细信息
We show that there are simplex pivoting rules for which it is PSPACE-complete to tell if a particular basis will appear on the algorithm's path. Such rules cannot be the basis of a strongly polynomial algorithm, u...
详细信息
For a mixed integer linear program where all integer variables are bounded, we study a reformulation introduced by Roy that maps general integer variables to a collection of binary variables. We study theoretical prop...
详细信息
暂无评论