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

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

来源：评论

学校读者我要写书评

暂无评论

Partial Convexification of General MIPs by Dantzig-Wolfe Reformulation

引用

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

作者： Bergner, Martin Caprara, Alberto Furini, Fabio Luebbecke, Marco E. Malaguti, Enrico Traversi, Emiliano Rhein Westfal TH Aachen Chair Operat Res Templergraben 64 D-52056 Aachen Germany Univ Bologna DEIS Viale Risorgimento 2 I-40136 Bologna Italy

ISBN: (纸本)9783642208072

Dantzig-Wolfe decomposition is well-known to provide strong dual bounds for specially structured mixed integer programs (MIPs) in practice. However, the method is not implemented in any state-of-the-art MIP solver: it needs tailoring to the particular problem;the decomposition must be determined from the typical bordered block-diagonal matrix structure;the resulting column generation subproblems must be solved efficiently;etc. We provide a computational proof-of-concept that the process can be automated in principle, and that strong dual bounds can be obtained on general MIPs for which a solution by a decomposition has not been the first choice. We perform an extensive computational study on the 0-1 dynamic knapsack problem (without block-diagonal structure) and on general MIPLIB2003 instances. Our results support that Dantzig-Wolfe reformulation may hold more promise as a general-purpose tool than previously acknowledged by the research community.

关键词： integer programming

来源：评论

学校读者我要写书评

暂无评论

Optimal deployment of eventually-serializable data services

引用

ANNALS OF OPERATIONS RESEARCH 2011年第1期184卷 273-294页

作者： Michel, L. Shvartsman, A. Sonderegger, E. Van Hentenryck, P. Univ Connecticut Storrs CT 06269 USA Brown Univ Providence RI 02912 USA

Providing consistent and fault-tolerant distributed object services is among the fundamental problems in distributed computing. To achieve fault-tolerance and to increase throughput, objects are replicated at different networked nodes. However, replication induces significant communication costs to maintain replica consistency. Eventually-Serializable Data Service (ESDS) has been proposed to reduce these costs and enable fast operations on data, while still providing guarantees that the replicated data will eventually be consistent. this paper reconsiders the deployment phase of ESDS, in which a particular implementation of communicating software components must be mapped onto a physical architecture. this deployment aims at minimizing the overall communication costs, while satisfying the constraints imposed by the protocol. Both MIP (Mixed integer programming) and CP (Constraint programming) models are presented and applied to realistic ESDS instances. the experimental results indicate that both models can find optimal solutions and prove optimality. the CP model, however, provides orders of magnitude improvements in efficiency. the limitations of the MIP model and the critical aspects of the CP model are discussed. Symmetry breaking and parallel computing are also shown to bring significant benefits.

关键词： FAULT-tolerant computing DISTRIBUTED computing DATA replication COMMUNICATION integer programming CONSTRAINT programming (Computer science) SOFTWARE

来源：评论

学校读者我要写书评

暂无评论

Jump Number of Two-Directional Orthogonal Ray Graphs

引用

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

作者： Soto, Jose A. Telha, Claudio MIT Dept Math Cambridge MA 02139 USA MIT Ctr Operat Res Cambridge MA USA

ISBN: (纸本)9783642208072

We model maximum cross-free matchings and minimum biclique covers of two-directional orthogonal ray graphs (2-dorgs) as maximum independent sets and minimum hitting sets of an associated family of rectangles in the plane, respectively. We then compute the corresponding maximum independent set using linear programming and uncrossing techniques. this procedure motivates an efficient combinatorial algorithm to find a cross-free matching and a biclique cover of the same cardinality, proving the corresponding min-max relation. We connect this min-max relation with thework ofGyori [19], Lubiw[23], and Frank and Jordan [16] on seemingly unrelated problems. Our result can be seen as a non-trivial application of Frank and Jord ' an's theorem. As a direct consequence, we obtain the first polynomial algorithm for the jump number problem on 2-dorgs. For the subclass of convex graphs, our approach is a vast improvement over previous algorithms. Additionally, we prove that the weighted maximum cross-free matching problem is NP-complete for 2-dorgs and give polynomial algorithms for some subclasses.

关键词： Linear programming

来源：评论

学校读者我要写书评

暂无评论

Design and Verify: A New Scheme for Generating Cutting-Planes

引用

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

作者： Dey, Santanu S. Pokutta, Sebastian Georgia Inst Technol H Milton Stewart Sch Ind & Syst Engn Atlanta GA 30332 USA MIT Sloan Sch Management Cambridge MA 02139 USA

ISBN: (纸本)9783642208072

A cutting-plane procedure for integer programming (IP) problems usually involves invoking a black-box procedure (such as the Gomory-Chvatal (GC) procedure) to compute a cutting-plane. In this paper, we describe an alternative paradigm of using the same cutting-plane black-box. this involves two steps. In the first step, we design an inequality cx <= d, independent of the cutting-plane black-box. In the second step, we verify that the designed inequality is a valid inequality by verifying that the set P boolean AND {x is an element of R-n : cx >= d + 1} boolean AND Z(n) is empty using cutting-planes from the black-box. Here P is the feasible region of the linear-programming relaxation of the IP. We refer to the closure of all cutting-planes that can be verified to be valid using a specific cutting-plane black-box as the verification closure of the considered cutting-plane black-box. this paper conducts a systematic study of properties of verification closures of various cutting-plane black-box procedures.

关键词： Verification Scheme Cutting-Planes integer programming

来源：评论

学校读者我要写书评

暂无评论

8th international conference on Integration of AI and OR Techniques in Constraint programming for combinatorial optimization Problems, CPAIOR 2011

8th International Conference on Integration of AI and OR Tec...

引用

8th international conference on Integration of AI and OR Techniques in Constraint programming for combinatorial optimization Problems, CPAIOR 2011

ISBN: (纸本)9783642213106

the proceedings contain 23 papers. the special focus in this conference is on Integration of AI and OR Techniques in Constraint programming for combinatorial optimization Problems. the topics include: Branch-cut-and-propagate for the maximum k-colorable subgraph problem with symmetry;climbing depth-bounded adjacent discrepancy search for solving hybrid flow shop scheduling problems with multiprocessor tasks;on counting lattice points and chvátal-gomory cutting planes;precedence constraint posting for cyclic scheduling problems;A probing algorithm for MINLP with failure prediction by SVM;recovering indirect solution densities for counting-based branching heuristics;using hard constraints for representing soft constraints;the objective sum constraint;almost square packing;propagation in constraints: How one thing leads to another;efficient planning of substation automation system cables;a new algorithm for linear and integer feasibility in horn constraints;timetable edge finding filtering algorithm for discrete cumulative resources;identifying patterns in sequences of variables;on bilevel programming and its impact in branching, cutting and complexity;optimization methods for the partner units problem;Manipulating MDD relaxations for combinatorial optimization;the alldifferent constraint with precedences;retail store workforce scheduling by expected operating income maximization;Spatial and Objective decompositions for very large SCAPs;upgrading shortest paths in networks.

关键词：

来源：评论

学校读者我要写书评

暂无评论

Efficient Algorithms for Finding the k Most Vital Edges for the Minimum Spanning Tree Problem

Efficient Algorithms for Finding the <i>k</i> Most Vital Edg...

引用

5th Annual international conference on combinatorial optimization and Applications (COCOA 2011)

作者： Bazgan, Cristina Toubaline, Sonia Vanderpooten, Daniel Univ Paris 09 LAMSADE F-75775 Paris 16 France

ISBN: (纸本)9783642226151

We study in this paper the problem of finding in a graph a subset of k edges whose deletion causes the largest increase in the weight of a minimum spanning tree. We propose for this problem an explicit enumeration algorithm whose complexity, when compared to the current best algorithm, is better for general k but very slightly worse for fixed k. More interestingly, unlike in the previous algorithms, we can easily adapt our algorithm so as to transform it into an implicit exploration algorithm based on a branch and bound scheme. We also propose a mixed integer programming formulation for this problem. Computational results show a clear superiority of the implicit enumeration algorithm both over the explicit enumeration algorithm and the mixed integer program.

关键词： most vital edges minimum spanning tree exact algorithms mixed integer program

来源：评论

学校读者我要写书评

暂无评论

Backdoor Branching

引用

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

作者： Fischetti, Matteo Monaci, Michele Univ Padua DEI Via Gradenigo 6-A I-35131 Padua Italy

ISBN: (纸本)9783642208072

Which is the minimum number of variables that need branching for a given MIP instance? Can this information be effective in producing compact branching trees, hence improving the performance of a state-of-the-art solver? In this paper we present a restart exact MIP solution scheme where a set covering model is used to find a small set of variables (a "backdoor", in the terminology of [8]) to be used as first-choice variables for branching. In a preliminary "sampling" phase, our method quickly collects a number of relevant low-cost fractional solutions that qualify as obstacles for LP bound improvement. then a set covering model is solved to detect a small subset of variables (the backdoor) that "cover the fractionality" of the collected fractional solutions. these backdoor variables are put in a priority branching list, and a black-box MIP solver is eventually run-in its default mode-by taking this list into account, thus avoiding any other interference with its highly-optimized internal mechanisms. Computational results on a large set of instances from MIPLIB 2010 are presented, showing that some speedup can be achieved even with respect to a state-of-the-art solver such as IBM ILOG Cplex 12.2.

关键词： integer programming

来源：评论

学校读者我要写书评

暂无评论

Optimal Caching Router Placement for Reduction in Retransmission Delay

Optimal Caching Router Placement for Reduction in Retransmis...

引用

20th international conference on Computer Communications and Networks (ICCCN)

作者： McGarry, Michael P. Shakya, Rosish Ohannessian, Mesrob I. Ferzli, Rony Univ Texas El Paso Dept Elect & Comp Engn El Paso TX 79968 USA Univ Akron Dept Elect & Comp Engn Akron OH 44325 USA MIT Dept Comp Sci & Elect Engn Cambridge MA USA Microsoft Corp Unified Comm Grp Redmond WA 98052 USA

ISBN: (纸本)9781457706387

We analyze the use of caching of video frames at network routers for reducing average retransmission delay. We formulate an expression for the average retransmission delay using video caching routers. In turn, we use this expression to formulate a mathematical program to minimize the average retransmission delay. We find a dynamic programming solution to the resultant non-linear convex binary integer program. We compare the results obtained from the dynamic programming solution with those obtained via experimental exhaustive enumeration. the experimental results validate our models and dynamic programming solution. Finally, we use numerical analysis to quantify the retransmission delay difference between the best and worst caching router placements. Our findings show that the optimal placement of caching routers can significantly reduce cost by minimizing the number of caching routers required to meet a desired retransmission delay performance. Furthermore, our dynamic programming solution shows that such optimal placement can be efficiently determined from network parameters, without an exhaustive search.

关键词： Multimedia networking Video networking Caching Routing Retransmission delay optimization combinatorial optimization Dynamic programming

来源：评论

学校读者我要写书评

暂无评论

An Excluded Minor Characterization of Seymour Graphs

引用

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

作者： Ageev, Alexander Benchetrit, Yohann Sebo, Andras Szigeti, Zoltan Sobolev Inst Math Novosibirsk Russia Lab G SCOP Grenoble France

ISBN: (纸本)9783642208072

A graph G is said to be a Seymour graph if for any edge set F there exist vertical bar F vertical bar pairwise disjoint cuts each containing exactly one element of F, provided for every circuit C of G the necessary condition vertical bar C boolean AND F vertical bar = vertical bar C\F vertical bar is satisfied. Seymour graphs behave well with respect to some integer programs including multiflow problems, or more generally odd cut packings, and are closely related to matching theory. A first coNP characterization of Seymour graphs has been shown by Ageev, Kostochka and Szigeti [1], the recognition problem has been solved in a particular case by Gerards [2], and the related cut packing problem has been solved in the corresponding special cases. In this article we show a new, minor-producing operation that keeps this property, and prove excluded minor characterizations of Seymour graphs: the operation is the contraction of full stars, or of odd circuits. this sharpens the previous results, providing at the same time a simpler and self-contained algorithmic proof of the existing characterizations as well, still using methods of matching theory and its generalizations.

关键词： integer programming

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：