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

Branch-Cut-and-Propagate for the Maximum k-Colorable Subgraph Problem with Symmetry

Branch-Cut-and-Propagate for the Maximum k-Colorable Subgrap...

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

作者： Januschowski, Tim Pfetsch, Marc E. Natl Univ Ireland Univ Coll Cork Cork Constraint Computat Ctr Dept Comp Sci Cork Ireland Tech Univ Carolo Wilhelmina Braunschweig Inst Math Optimizat D-38106 Braunschweig Germany

ISBN: (纸本)9783642213113

Given an undirected graph and a positive integer k, the maximum k-colorable subgraph problem consists of selecting a k-colorable induced subgraph of maximum cardinality. the natural integer programming formulation for this problem exhibits two kinds of symmetry: arbitrarily permuting the color classes and/or applying a non-trivial graph automorphism gives equivalent solutions. It is well known that such symmetries have negative effects on the performance of constraint/integer programming solvers. We investigate the integration of a branch-and-cut algorithm for solving the maximum k-colorable subgraph problem with constraint propagation techniques to handle the symmetry arising from the graph. the latter symmetry is handled by (non-linear) lexicographic ordering constraints and linearizations thereof. In experiments, we evaluate the influence of several components of our algorithm on the performance, including the different symmetry handling methods. We show that several components are crucial for an efficient algorithm;in particular, the handling of graph symmetries yields a significant performance speed-up.

关键词： integer programming

来源：评论

学校读者我要写书评

暂无评论

Facility Location with Client Latencies: Linear programming Based Techniques for Minimum Latency Problems

引用

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

作者： Chakrabarty, Deeparnab Swamy, Chaitanya Univ Penn Deptartment CIS Philadelphia PA 19104 USA Univ Waterloo Combinator & Optimizat Waterloo ON N2L 3G1 Canada

ISBN: (纸本)9783642208072

We introduce a problem that is a common generalization of the uncapacitated facility location and minimum latency (ML) problems, where facilities need to be opened to serve clients and also need to be sequentially activated before they can provide service. Formally, we are given a set F of n facilities with facility-opening costs f(i), a set D of m clients, connection costs c(ij) specifying the cost of assigning a client j to a facility i, a root node r denoting the depot, and a time metric d on F.{r}. Our goal is to open a subset F of facilities, find a path P starting at r and spanning F to activate the open facilities, and connect each client j to a facility phi(j) epsilon F, so as to minimize Sigma(i epsilon F) f(i) + Sigma(j epsilon D)(c(phi(j)),(j) + t(j)), where t(j) is the time taken to reach phi(j) along path P. We call this the minimum latency uncapacitated facility location (MLUFL) problem. Our main result is an O(log n . max(log n, logm))-approximation for MLUFL. We also show that any improvement in this approximation guarantee, implies an improvement in the (current-best) approximation factor for group Steiner tree. We obtain constant approximations for two natural special cases of the problem: (a) related MLUFL (metric connection costs that are a scalar multiple of the time metric);(b) metric uniform MLUFL (metric connection costs, uniform time-metric). Our LP-based methods are versatile and easily adapted to yield approximation guarantees for MLUFL in various more general settings, such as (i) when the latency-cost of a client is a function of the delay faced by the facility to which it is connected;and (ii) the k-route version, where k vehicles are routed in parallel to activate the open facilities. Our LP-based understanding of MLUFL also offers some LP-based insights into ML, which we believe is a promising direction for obtaining improvements for ML.

关键词： Location

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Branched Polyhedral Systems

Branched Polyhedral Systems

引用

14th international conference integer programming and combinatorial optimization

作者： Kaibel, Volker Loos, Andreas Otto von Guericke Univ Inst Math Optimierung D-39108 Magdeburg Germany

ISBN: (纸本)9783642130359

We introduce the framework of branched polyhedral systems that can be used in order to construct extended formulations for polyhedra by combining extended formulations for other polyhedra. the framework, for instance, simultaneously generalizes extended formulations like the well-known ones (see Balas [1]) for the convex hulls of unions of polyhedra (disjunctive programming) and like those obtained from dynamic programming algorithms for combinatorial optimization problems (due to Martin, Rardin, and Campbell [11]). Using the framework, we construct extended formulations for full orbitopes (the convex hulls of all 0/1-matrices with lexicographically sorted columns), we show for two special matching problems, how branched polyhedral systems can be exploited in order to construct formulations for certain nested combinatorial problems, and we indicate how one can build extended formulations for stable set polytopes using the framework of branched polyhedral systems.

关键词： Dynamic programming

来源：评论

学校读者我要写书评

暂无评论

integer programming and combinatorial optimization - 13th international conference, ipco 2008, Proceedings

引用

13th international conference on integer programming and combinatorial optimization, ipco 2008

ISBN: (纸本)3540688862

the proceedings contain 32 papers. the topics discussed include: perspective relaxation of mixed integer nonlinear programs with indicator variables;disjunctive cuts for non-convex mixed integer quadratically constrained programs;the air traffic flow management problem: an integer optimization approach;the induced disjoint paths problem;a new algorithm for the maximum weighted stable set problem in claw-free graphs;a polynomial algorithm for weighted abstract flow;a comparative study of linear and semidefinite branch-and-cut methods for solving the minimum graph bisection problem;binary positive semidefinite matrices and associated integer polytopes;vertex cover resists SDPs tightened by local hypermetric inequalities;tight bounds for permutation flow shop scheduling;the stochastic machine replenishment problem;a polynomial time approximation scheme for the square packing problem;and constraint orbital branching.

关键词： integer programming

来源：评论

学校读者我要写书评

暂无评论

integer programming and combinatorial optimization: 12th international ipco conference, Proceedings

引用

12th international conference on integer programming and combinatorial optimization, ipco XII

ISBN: (纸本)9783540727910

the proceedings contain 36 papers. the topics discussed include: inequalities from two rows of a simplex tableau;cuts for conic mixed-integer programming;sequential-merge facets for two-dimensional group problems;triangle-free simple 2-matchings in subcubic graphs;the smoothed number of Pareto optimal solutions in bicriteria integer optimization;finding a polytope from its graph in polynomial time;orbitopal fixing;orbital branching;distinct triangle areas in a planar point set;scheduling with precedence constraints of low fractional dimension;approximation algorithms for 2-stage stochastic scheduling problems;on integer programming and the branch-width of the constraint matrix;matching problems in polymatroids without double circuits;maximizing a submodular set function subject to a matroid constraint;on a generalization of the master cyclic group polyhedron;and a framework to derive multidimensional superadditive lifting functions and its applications.

关键词： Linear programming

来源：评论

学校读者我要写书评

暂无评论

ON SEMIDEFINITE programming RELAXATIONS OF thE TRAVELING SALESMAN PROBLEM

引用

SIAM JOURNAL ON optimization 2008年第4期19卷 1559-1573页

作者： De Klerk, Etienne Pasechnik, Dmitrii V. Sotirov, Renata Tilburg Univ Dept Econometr & OR NL-5000 LE Tilberg Netherlands Nanyang Technol Univ Sch Phys & Math Sci Singapore Singapore

We consider a new semidefinite programming (SDP) relaxation of the symmetric traveling salesman problem (TSP) that may be obtained via an SDP relaxation of the more general quadratic assignment problem (QAP). We show that the new relaxation dominates the one in [D. Cvetkovic, M. Cangalovic, and V. Kovacevic-Vujcic, Semidefinite programming methods for the symmetric traveling salesman problem, in Proceedings of the 7th international ipco conference on integer programming and combinatorial optimization, Springer-Verlag, London, UK, 1999, pp. 126-136]. Unlike the bound of Cvetkovic et al., the new SDP bound is not dominated by the Held-Karp linear programming bound, or vice versa.

关键词： traveling salesman problem semidefinite programming quadratic assignment problem association schemes

来源：评论

学校读者我要写书评

暂无评论

Lifting integer variables in minimal inequalities corresponding to lattice-free triangles

引用

13th international conference on integer programming and combinatorial optimization

作者： Dey, Santanu S. Wolsey, Laurence A. CORE 34 Voie Roman Pays B-1348 Louvain Belgium Catholic Univ Louvain CORE & INMA B-1348 Louvain Belgium

ISBN: (纸本)9783540688860

Recently, Andersen et al. [1] and Borozan and Cornuejols [3] characterized the minimal inequalities of a system of two rows with two free integer variables and nonnegative continuous variables. these inequalities are either split cuts or intersection cuts derived using maximal lattice-free convex sets. In order to use these minimal inequalities to obtain cuts from two rows of a general simplex tableau, it is necessary to extend the system to include integer variables (giving the two-dimensional mixed integer infinite group problem), and to develop lifting functions giving the coefficients of the integer variables in the corresponding inequalities. In this paper, we analyze the lifting of minimal inequalities derived from lattice-free triangles. Maximal lattice-free triangles in R-2 can be classified into three categories: those with multiple integral points in the relative interior of one of its sides, those with integral vertices and one integral point in the relative interior of each side, and those with non integral vertices and one integral point in the relative interior of each side. We prove that the lifting functions are unique for each of the first two categories such that the resultant inequality is minimal for the mixed integer infinite group problem, and characterize them. We show that the lifting function is not necessarily unique in the third category. For this category we show that a fill-in inequality (Johnson [11]) yields minimal inequalities for mixed integer infinite group problem under certain sufficiency conditions. Finally, we present conditions for the fill-in inequality to be extreme.

关键词： Set theory

来源：评论

学校读者我要写书评

暂无评论

Structural identifiability in low-rank matrix factorization

Structural identifiability in low-rank matrix factorization

引用

14th Annual international conference on Computing and Combinatorics (COCOON 2008)

作者： Fritzilas, Epameinondas Rios-Solis, Yasmin A. Rahmann, Sven Univ Bielefeld Fac Technol D-4800 Bielefeld Germany Tech Univ Dortmund Comp Sci 11 D-44221 Dortmund Germany

ISBN: (纸本)9783540697329

In many signal processing and data mining applications, we need to approximate a given matrix Y of "sensor measurements" over several experiments by a low-rank product Y approximate to A (.) X, where X contains source signals for each experiment, A contains source-sensor mixing coefficients, and both A and X are unknown. We assume that the only a-priori information available is that A must have zeros at certain positions;this constrains the source-sensor network connectivity pattern. In general, different AX factorizations approximate a given Y equally well, so a fundamental question is how the connectivity restricts the solution space. We present a combinatorial characterization of uniqueness up to diagonal scaling, called structural identifiability of the model, using the concept of structural rank from combinatorial matrix theory. Next, we define an optimization problem that arises in the need for efficient experimental design: to minimize the number of sensors while maintaining structural identifiability. We prove its NP-hardness and present a mixed integer linear programming framework with two cutting-plane approaches. Finally, we experimentally compare these approaches on simulated instances of various sizes.

关键词： Sensor networks

来源：评论

学校读者我要写书评

暂无评论

integer programming and combinatorial optimization: 11th international ipco conference. Proceedings

Integer Programming and Combinatorial Optimization: 11th Int...

引用

11th international ipco conference on integer programming and combinatorial optimization

the proceedings contain 34 papers from the integer programming and combinatorial optimization: 11th international ipco conference, Proceedings. the topics discussed include: mixed-integer cuts from cyclic groups;optimization over the first chvátal closure;a combinatorial algorithm to find a maximum even factor;improved approximation schemes for linear programming relaxations of combinatorial optimization problems;on the approximability of the minimum congestion unsplittable shortest path routing problem;inventory and facility location models with market selection;and on approximation complex quadratic optimization problems via semidefinite programming relaxations.

关键词： integer programming

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：