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

Extended Formulations in Mixed-integer Convex programming 1

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

作者： Lubin, Miles Yamangil, Emre Bent, Russell Vielma, Juan Pablo MIT 77 Massachusetts Ave Cambridge MA 02139 USA Los Alamos Natl Lab Los Alamos NM USA

ISBN: (数字)9783319334615

ISBN: (纸本)9783319334615;9783319334608

We present a unifying framework for generating extended formulations for the polyhedral outer approximations used in algorithms for mixed-integer convex programming (MICP). Extended formulations lead to fewer iterations of outer approximation algorithms and generally faster solution times. First, we observe that all MICP instances from the MINLPLIB2 benchmark library are conic representable with standard symmetric and nonsymmetric cones. Conic reformulations are shown to be effective extended formulations themselves because they encode separability structure. For mixed-integer conic-representable problems, we provide the first outer approximation algorithm with finite-time convergence guarantees, opening a path for the use of conic solvers for continuous relaxations. We then connect the popular modeling framework of disciplined convex programming (DCP) to the existence of extended formulations independent of conic representability. We present evidence that our approach can yield significant gains in practice, with the solution of a number of open instances from the MINLPLIB2 benchmark library.

关键词： Convex optimization

来源：评论

学校读者我要写书评

暂无评论

Intersection Cuts for Bilevel optimization 1

引用

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

作者： Fischetti, Matteo Ljubic, Ivana Monaci, Michele Sinnl, Markus Univ Padua DEI Padua Italy ESSEC Business Sch Paris Cergy Pontoise France Univ Vienna ISOR Vienna Austria

ISBN: (数字)9783319334615

ISBN: (纸本)9783319334615;9783319334608

the exact solution of bilevel optimization problems is a very challenging task that received more and more attention in recent years, as witnessed by the flourishing recent literature on this topic. In this paper we present ideas and algorithms to solve to proven optimality generic Mixed-integer Bilevel Linear Programs (MIBLP's) where all constraints are linear, and some/all variables are required to take integer values. In doing so, we look for a general-purpose approach applicable to any MIBLP (under mild conditions), rather than ad-hoc methods for specific cases. Our approach concentrates on minimal additions required to convert an effective branch-and-cut MILP exact code into a valid MIBLP solver, thus inheriting the wide arsenal of MILP tools (cuts, branching rules, heuristics) available in modern solvers.

关键词： Arsenals

来源：评论

学校读者我要写书评

暂无评论

Towards the price of leasing online

引用

JOURNAL OF combinatorial optimization 2016年第4期32卷 1197-1216页

作者： Abshoff, Sebastian Kling, Peter Markarian, Christine Heide, Friedhelm Meyer Auf Der Pietrzyk, Peter Univ Paderborn Dept Comp Sci Furstenallee 11 D-33102 Paderborn Germany Univ Paderborn Heinz Nixdorf Inst Furstenallee 11 D-33102 Paderborn Germany Simon Fraser Univ Sch Comp Sci 8888 Univ Dr Burnaby BC V5A 1S6 Canada

We consider online optimization problems in which certain goods have to be acquired in order to provide a service or infrastructure. Classically, decisions for such problems are considered as final: one buys the goods. However, in many real world applications, there is a shift away from the idea of buying goods. Instead, leasing is often a more flexible and lucrative business model. Research has realized this shift and recently initiated the theoretical study of leasing models (Anthony and Gupta in Proceedings of the integer programming and combinatorial optimization: 12th international ipco conference, Ithaca, NY, USA, June 25-27, 2007;Meyerson in Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 23-25 Oct 2005, Pittsburgh, PA, USA, 2005;Nagarajan and Williamson in Discret Optim 10(4):361-370, 2013) We extend this line of work and suggest a more systematic study of leasing aspects for a class of online optimization problems. We provide two major technical results. We introduce the leasing variant of online set multicover and give an -competitive algorithm (with n, m, and K being the number of elements, sets, and leases, respectively). Our results also imply improvements for the non-leasing variant of online set cover. Moreover, we extend results for the leasing variant of online facility location. Nagarajan and Williamson (Discret Optim 10(4):361-370, 2013) gave an -competitive algorithm for this problem (with n and K being the number of clients and leases, respectively). We remove the dependency on n (and, thereby, on time). In general, this leads to a bound of (with the maximal lease length ). For many natural problem instances, the bound improves to .

关键词： Online algorithms Set cover problems Facility location problems Primal dual algorithms Randomized rounding

来源：评论

学校读者我要写书评

暂无评论

Maximizing Monotone Submodular Functions over the integer Lattice 18th

Maximizing Monotone Submodular Functions over the Integer La...

引用

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

作者： Soma, Tasuku Yoshida, Yuichi Univ Tokyo Grad Sch Informat Sci & Technol Tokyo Japan Natl Inst Informat & Preferred Infrastruct Inc Tokyo Japan

ISBN: (纸本)9783319334615;9783319334608

the problem of maximizing non-negative monotone submodular functions under a certain constraint has been intensively studied in the last decade. In this paper, we address the problem for functions defined over the integer lattice. Suppose that a non-negative monotone submodular function f : Z(+)(n) -> R+ is given via an evaluation oracle. Assume further that f satisfies the diminishing return property, which is not an immediate consequence of the submodularity when the domain is the integer lattice. then, we show polynomial-time (1 - 1/e - epsilon)-approximation algorithm for cardinality constraints, polymatroid constraints, and knapsack constraints. For a cardinality constraint, we also show a (1 - 1/e - epsilon)-approximation algorithm with slightly worse time complexity that does not rely on the diminishing return property. Our algorithms for a polymatroid constraint and a knapsack constraint first extend the domain of the objective function to the Euclidean space and then run the continuous greedy algorithm. We give two different kinds of continuous extensions, one is for polymatroid constraints and the other is for knapsack constraints, which might be of independent interest.

关键词： Approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Valid Inequalities for Separable Concave Constraints with Indicator Variables 18th

Valid Inequalities for Separable Concave Constraints with In...

引用

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

作者： Lim, Cong Han Linderoth, Jeff Luedtke, James Univ Wisconsin Dept Comp Sci 1210 W Dayton St Madison WI 53706 USA Univ Wisconsin Dept Ind & Syst Engn Madison WI USA

ISBN: (纸本)9783319334615;9783319334608

We study valid inequalities for a set relevant for optimization models that have both binary indicator variables, which indicate positivity of associated continuous variables, and separable concave constraints. Such models reduce to a mixed-integer linear program (MILP) when the concave constraints are ignored, and to a nonconvex global optimization problem when the binary restrictions are ignored. In algorithms to solve such problems to global optimality, relaxations are traditionally obtained by using valid inequalities for the MILP ignoring the concave constraints, and by independently relaxing each concave constraint using the secant obtained from the bounds of the associated variable. We propose a technique to obtain valid inequalities that are based on both the MILP and the concave constraints. We begin by analyzing a low-dimensional set that contains a single binary indicator variable, a single concave constraint, and three continuous variables. Using this analysis, for the canonical Single Node Flow Set (SNFS), we demonstrate how to "tilt" a given valid inequality for the SNFS to obtain additional valid inequalities that account for separable concave functions of the arc flows. We present computational results demonstrating the utility of the new inequalities on a fixed plus concave cost transportation problem. To our knowledge, this is one of the first works that simultaneously convexifies both nonconvex functions and binary variables to strengthen the relaxations of practical mixed integer nonlinear programs.

关键词： Mixed integer nonlinear programming Global optimization Valid inequalities

来源：评论

学校读者我要写书评

暂无评论

integer programming and combinatorial optimization - 16th international conference, ipco 2013, Proceedings

引用

16th conference on integer programming and combinatorial optimization, ipco 2013

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.

关键词：

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Lower bounds on the sizes of integer programs without additional variables

引用

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

作者： Kaibel, Volker Weltge, Stefan Otto-von-Guericke-Universität Magdeburg Germany

ISBN: (纸本)9783319075563

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, corresponds to the smallest number of linear inequalities of any integer program having X as the set of feasible solutions that does not use auxiliary variables. We show that the use of auxiliary variables is essential for constructing polynomial size integer programming formulations in many relevant cases. In particular, we provide asymptotically tight exponential lower bounds on the relaxation complexity of the integer points of several well-known combinatorial polytopes, including the traveling salesman polytope and the spanning tree polytope. © 2014 Springer international Publishing Switzerland.

关键词： integer programming

来源：评论

学校读者我要写书评

暂无评论

Simple extensions of polytopes

引用

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

作者： Kaibel, Volker Walter, Matthias Otto-von-Guericke Universität Magdeburg Germany

ISBN: (纸本)9783319075563

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 combinatorial method to establish lower bounds on the simple extension complexity and show for several polytopes that they have large simple extension complexities. these examples include both the spanning tree and the perfect matching polytopes of complete graphs, uncapacitated flow polytopes for non-trivially decomposable directed acyclic graphs, and random 0/1-polytopes with vertex numbers within a certain range. On our way to obtain the result on perfect matching polytopes we improve on a result of Padberg and Rao's on the adjacency structures of those polytopes. © 2014 Springer international Publishing Switzerland.

关键词： Linear programming

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：