检索结果-内蒙古大学图书馆

integer programming and combinatorial optimization 1

丛书名： Lecture Notes in Computer Science

1000年

作者： Friedrich Eisenbrand Jochen Koenemann

this book constitutes the refereed proceedings of the 19th international conference on integer programming and combinatorial optimization, ipco 2017, held in Waterloo, IN, Canada, in June 2017.

ISBN: (数字)9783319592503

ISBN: (纸本)9783319592497

this book constitutes the refereed proceedings of the 19th international conference on integer programming and combinatorial optimization, ipco 2017, held in Waterloo, IN, Canada, in June 2017.

关键词： Numeric Computing Algorithm Analysis and Problem Complexity Discrete Mathematics in Computer Science Computer Communication Networks Artificial Intelligence

来源：评论

学校读者我要写书评

暂无评论

Mixed-integer Linear Representability, Disjunctions, and Variable Elimination 1

引用

19th international conference on integer programming and combinatorial optimization (ipco)

作者： Basu, Amitabh Martin, Kipp Ryan, Christopher thomas Wang, Guanyi Johns Hopkins Univ Dept Appl Math & Stat Baltimore MD 21218 USA Univ Chicago Booth Sch Business Chicago IL 60637 USA Georgia Inst Technol Ind & Syst Engn Atlanta GA 30332 USA

ISBN: (数字)9783319592503

ISBN: (纸本)9783319592503;9783319592497

Jeroslow and Lowe gave an exact geometric characterization of subsets of R-n that are projections of mixed-integer linear sets, a.k.a MILP-representable sets. We give an alternate algebraic characterization by showing that a set is MILP-representable if and only if the set can be described as the intersection of finitely many affine Chvatal inequalities. these inequalities are a modification of a concept introduced by Blair and Jeroslow. this gives a sequential variable elimination scheme that, when applied to the MILP representation of a set, explicitly gives the affine Chvatal inequalities characterizing the set. this is related to the elimination scheme of Wiliams and Williams-Hooker, who describe projections of integer sets using disjunctions of affine Chvatal systems. Our scheme extends their work in two ways. First, we show that disjunctions are unnecessary, by showing how to find the affine Chvatal inequalities that cannot be discovered by the Williams-Hooker scheme. Second, disjunctions of Chvatal systems can give sets that are not projections of mixed-integer linear sets;so the Williams-Hooker approach does not give an exact characterization of MILP representability.

关键词： integer programming

来源：评论

学校读者我要写书评

暂无评论

Discrete Newton's Algorithm for Parametric Submodular Function Minimization 1

引用

19th international conference on integer programming and combinatorial optimization (ipco)

作者： Goemans, Michel X. Gupta, Swati Jaillet, Patrick MIT Cambridge MA 02139 USA

ISBN: (数字)9783319592503

ISBN: (纸本)9783319592503;9783319592497

We consider the line search problem in a submodular polyhedron P(f)subset of R-n : Given an arbitrary a is an element of R-n and x(0) is an element of P(f), compute max{delta : x(0) + delta a is an element of P(f)}. the use of the discrete Newton's algorithm for this line search problem is very natural, but no strongly polynomial bound on its number of iterations was known (Iwata 2008). We solve this open problem by providing a quadratic bound of n(2) + O(n log(2) n) on its number of iterations. Our result considerably improves upon the only other known strongly polynomial time algorithm, which is based on Megiddo's parametric search framework and which requires (O) over bar (n(8)) submodular function minimizations (Nagano 2007). As a by-product of our study, we prove (tight) bounds on the length of chains of ring families and geometrically increasing sequences of sets, which might be of independent interest.

关键词： Discrete Newton's algorithm Submodular functions Line search Ring families Geometrically increasing sequence of sets Fractional combinatorial optimization

来源：评论

学校读者我要写书评

暂无评论

integer programming and Combinatoral optimization - 15th international conference, ipco 2011, Proceedings

引用

15th international conference on integer programming and combinatorial optimization, ipco 2011

ISBN: (纸本)9783642208065

the proceedings contain 33 papers. the topics discussed include: an excluded minor characterization of seymour graphs;complexity analyses of bienstock-zuckerberg and lasserre relaxations on the matching and stable set polytopes;a probabilistic analysis of the strength of the split and triangle closures;partial convexification of general MIPs by Dantzig-Wolfe reformulation;lift-and-project cuts for mixed integer convex programs;TSP on cubic and subcubic graphs;approximability of capacitated network design;facility location with client latencies: linear programming based techniques for minimum latency problems;an exact rational mixed-integer programming solver;valid inequalities for the pooling problem with binary variables;design and verify: a new scheme for generating cutting-planes;and contact center scheduling with strict resource requirements.

关键词：

来源：评论

学校读者我要写书评

暂无评论

Designing optimization Problems with Diverse Solutions 1

引用

24th international conference on integer programming and combinatorial optimization (ipco)

作者： Hanguir, Oussama Ma, Will Ryan, Christopher thomas Columbia Univ Ind Engn & Operat Res New York NY 10027 USA Columbia Univ Grad Sch Business New York NY 10027 USA Univ British Columbia UBC Sauder Sch Business Vancouver BC V6T 1Z2 Canada

ISBN: (数字)9783031327261

ISBN: (纸本)9783031327254;9783031327261

We consider the problem of designing a linear program that has diverse solutions as the right-hand side varies. this problem arises in video game settings where designers aim to have players use different "weapons" or "tactics" as they progress. We model this design question as a choice over the constraint matrix A and cost vector c to maximize the number of possible supports of unique optimal solutions (what we call "loadouts") of Linear Programs max{c(inverted perpendicular) x vertical bar Ax <= b, x >= 0} with nonnegative data considered over all resource vectors b. We provide an upper bound on the optimal number of loadouts and provide a family of constructions that have an asymptotically optimal number of loadouts. the upper bound is based on a connection between our problem and the study of triangulations of point sets arising from polyhedral combinatorics, and specifically the combinatorics of the cyclic polytope. Our asymptotically optimal construction also draws inspiration from the properties of the cyclic polytope.

关键词： linear programming triangulations diversity

来源：评论

学校读者我要写书评

暂无评论

Optimizing over the first Chvatal closure

引用

MAthEMATICAL programming 2007年第1期110卷 3-20页

作者： Fischetti, Matteo Lodi, Andrea Univ Padua DEI I-35131 Padua Italy Univ Bologna DEIS I-40136 Bologna Italy

How difficult is, in practice, to optimize exactly over the first Chvatal closure of a generic ILP? Which fraction of the integrality gap can be closed this way, e.g., for some hard problems in the MIPLIB library? Can the first-closure optimization be useful as a research (off-line) tool to guess the structure of some relevant classes of inequalities, when a specific combinatorial problem is addressed? In this paper we give answers to the above questions, based on an extensive computational analysis. Our approach is to model the rank-1 Chvatal-Gomory separation problem, which is known to be NP-hard, through a MIP model, which is then solved through a general-purpose MIP solver. As far as we know, this approach was never implemented and evaluated computationally by previous authors, though it gives a very useful separation tool for general ILP problems. We report the optimal value over the first Chvatal closure for a set of ILP problems from MIPLIB 3.0 and 2003. We also report, for the first time, the optimal solution of a very hard instance from MIPLIB 2003, namely nsrand-ipx, obtained by using our cut separation procedure to preprocess the original ILP model. Finally, we describe a new class of ATSP facets found with the help of our separation procedure.

关键词： integer programs separation problems Chvatal-Gomory cuts computational analysis

来源：评论

学校读者我要写书评

暂无评论

the triangle splitting method for biobjective mixed integer programming

引用

17th international conference on integer programming and combinatorial optimization, ipco 2014

作者： Boland, Natashia Charkhgard, Hadi Savelsbergh, Martin School of Mathematical and Physical Sciences University of Newcastle NSW 2308 Australia

ISBN: (纸本)9783319075563

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 converges quickly to the complete set of nondominated points. A computational study demonstrates the efficacy of the triangle splitting method. © 2014 Springer international Publishing Switzerland.

关键词： integer programming

来源：评论

学校读者我要写书评

暂无评论

On the Partial Convexification of the Low-Rank Spectral optimization: Rank Bounds and Algorithms 25th

On the Partial Convexification of the Low-Rank Spectral Opti...

引用

25th international conference on integer programming and combinatorial optimization (ipco)

作者： Li, Yongchun Xie, Weijun Georgia Inst Technol H Milton Stewart Sch Ind & Syst Engn Atlanta GA 30332 USA

ISBN: (纸本)9783031598340;9783031598357

A Low-rank Spectral optimization Problem (LSOP) minimizes a linear objective function subject to multiple two-sided linear inequalities intersected with a low-rank and spectral constrained domain. Although solving LSOP is, in general, NP-hard, its partial convexification (i.e., replacing the domain by its convex hull) termed "LSOP-R", is often tractable and yields a high-quality solution. this motivates us to study the strength of LSOP-R. Specifically, we derive rank bounds for any extreme point of the feasible set of LSOP-R with different matrix spaces and prove their tightness. the proposed rank bounds recover two well-known results in the literature from a fresh angle and allow us to derive sufficient conditions under which the relaxation LSOP-R is equivalent to LSOP. To effectively solve LSOP-R, we develop a column generation algorithm with a vector-based convex pricing oracle, coupled with a rank-reduction algorithm, which ensures that the output solution always satisfies the theoretical rank bound. Finally, we numerically verify the strength of LSOP-R and the efficacy of the proposed algorithms.

关键词： Linear programming

来源：评论

学校读者我要写书评

暂无评论

Semidefinite and Linear programming Integrality Gaps for Scheduling Identical Machines 1

引用

18th international conference on integer programming and combinatorial optimization (ipco)

作者： Kurpisz, Adam Mastrolilli, Monaldo Mathieu, Claire Moemke, Tobias Verdugo, Victor Wiese, Andreas Dalle Molle Inst Artificial Intelligence Res Manno Switzerland Ecole Normale Super CNRS UMR 8548 Dept Comp Sci Paris France Univ Saarland Dept Comp Sci Saarbrucken Germany Univ Chile Dept Ind Engn Santiago Chile Max Planck Inst Informat Saarbrucken Germany

ISBN: (数字)9783319334615

ISBN: (纸本)9783319334615;9783319334608

Sherali-Adams [25] and Lovasz-Schrijver [21] developed systematic procedures to strengthen a relaxation known as lift-and-project methods. they have been proven to be a strong tool for developing approximation algorithms, matching the best relaxations known for problems like Max-Cut and Sparsest-Cut. In this work we provide lower bounds for these hierarchies when applied over the configuration LP for the problem of scheduling identical machines to minimize the makespan. First we show that the configuration LP has an integrality gap of at least 1024/1023 by providing a family of instances with 15 different job sizes. then we show that for any integer n there is an instance with n jobs in this family such that after Omega(n) rounds of the Sherali-Adams (SA) or the Lovasz-Schrijver (LS+) hierarchy the integrality gap remains at least 1024/1023.

关键词： Linear programming

来源：评论

学校读者我要写书评

暂无评论

A New Approach to the Stable Set Problem Based on Ellipsoids

引用

15th international conference on integer programming and combinatorial optimization (ipco)

作者： Giandomenico, Monia Letchford, Adam N. Rossi, Fabrizio Smriglio, Stefano Univ Aquila Dept Comp Sci Laquila Italy Univ Lancaster Dept Management Sci Lancaster England

ISBN: (纸本)9783642208072

A new exact approach to the stable set problem is presented, which attempts to avoids the pitfalls of existing approaches based on linear and semidefinite programming. the method begins by constructing an ellipsoid that contains the stable set polytope and has the property that the upper bound obtained by optimising over it is equal to the Lovasz theta number. this ellipsoid is then used to derive cutting planes, which can be used within a linear programming-based branch-and-cut algorithm. Preliminary computational results indicate that the cutting planes are strong and easy to generate.

关键词： stable set problem semidefinite programming convex quadratic programming cutting planes

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：