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

The location-dispatching problem: Polyhedral results and content delivery network design

DISCRETE APPLIED MATHEMATICS 2014年第Part1期164卷 68-85页

作者： Chretienne, Philippe Fouilhoux, Pierre Gourdin, Eric Segura, Jean-Mathieu Univ Paris 06 Lab LIP6 F-75005 Paris France France Telecom R&D Orange Labs F-92794 Issy Les Moulineaux 9 France

Let G = (V, A) be a directed graph and F be a set of items. The Location-Dispatching Problem consists of determining subsets L-1 subset of F F located at nodes i is an element of V, minimizing the sum of two costs: a piecewise linear installation cost associated with L-1 and an access cost for each node of V to reach a copy of each item of F. We formulate this problem as a linear program with binary variables x and integer variables z. We propose a facial study of the associated polytope and we introduce the so-called integrity hop cost inequalities that force z to be an integer as soon as x is binary. Using this, we devise a branch-andcut algorithm and report some experimental results. This algorithm has been used to solve Content Delivery Network instances in order to optimize a Video On Demand (VoD) system. (C) 2012 Elsevier B.V. All rights reserved.

关键词： Location Integer program Polytope branch-and-cut algorithm CDN design

来源：评论

学校读者我要写书评

暂无评论

The location-dispatching problem: Polyhedral results and content delivery network design

The location-dispatching problem: Polyhedral results and con...

引用

1st International Symposium on Combinatorial Optimization (ISCO)

作者： Chretienne, Philippe Fouilhoux, Pierre Gourdin, Eric Segura, Jean-Mathieu Univ Paris 06 Lab LIP6 F-75005 Paris France France Telecom R&D Orange Labs F-92794 Issy Les Moulineaux 9 France

关键词： Location Integer program Polytope branch-and-cut algorithm CDN design

来源：评论

学校读者我要写书评

暂无评论

Benders Decomposition for the Hop-Constrained Survivable Network Design Problem

引用

INFORMS JOURNAL ON COMPUTING 2013年第1期25卷 13-26页

作者： Botton, Quentin Fortz, Bernard Gouveia, Luis Poss, Michael Catholic Univ Louvain Ctr Supply Chain Management Louvain Sch Management B-1348 Louvain Belgium Catholic Univ Louvain Ctr Operat Res & Econometr B-1348 Louvain Belgium Univ Libre Bruxelles Fac Sci Dept Comp Sci B-1050 Brussels Belgium Univ Lisbon Fac Ciencias Ctr Invest Operac Dept Estat Invest Operac P-1749016 Lisbon Portugal

Given a graph with nonnegative edge weights and node pairs Q, we study the problem of constructing minimum weight set of edges so that the induced subgraph contains at least K edge-disjoint paths containing at most L edges between each pair in Q. Using the layered representation introduced by Gouveia [Gouveia, L. 1998. Using variable redefinition for computing lower bounds for minimum spanning and Steiner trees with hop constraints. INFORMS J. Comput. 10(2) 180-188], we present a formulation for the problem valid for any K, L >= 1. We use a Benders decomposition method to efficiently handle the large number of variables and constraints. We show that our Benders cuts contain constraints used in previous studies to formulate the problem for L = 2, 3, 4, as well as new inequalities when L >= 5. Whereas some recent works on Benders decomposition study the impact of the normalization constraint in the dual subproblem, we focus here on when to generate the Benders cuts. We present a thorough computational study of various branch-and-cut algorithms on a large set of instances including the real-based instances from SNDlib. Our best branch-and-cut algorithm combined with an efficient heuristic is able to solve the instances significantly faster than CPLEX 12 on the extended formulation.

关键词： survivable network edge-disjoint paths hop-constrained paths Benders decomposition branch-and-cut algorithm

来源：评论

学校读者我要写书评

暂无评论

Stochastic binary problems with simple penalties for capacity constraints violations

引用

MATHEMATICAL PROGRAMMING 2013年第1-2期138卷 199-221页

作者： Fortz, B. Labbe, M. Louveaux, F. Poss, M. Univ Libre Brussels Fac Sci Dept Comp Sci Brussels Belgium Univ Namur FUNDP Dept Business Adm Namur Belgium Univ Coimbra Dept Math CMUC P-3001454 Coimbra Portugal

This paper studies stochastic programs with first-stage binary variables and capacity constraints, using simple penalties for capacities violations. In particular, we take a closer look at the knapsack problem with weights and capacity following independent random variables and prove that the problem is weakly -hard in general. We provide pseudo-polynomial algorithms for three special cases of the problem: constant weights and capacity uniformly distributed, subset sum with Gaussian weights and strictly positively distributed random capacity, and subset sum with constant weights and arbitrary random capacity. We then turn to a branch-and-cut algorithm based on the outer approximation of the objective function. We provide computational results for the stochastic knapsack problem (i) with Gaussian weights and constant capacity and (ii) with constant weights and capacity uniformly distributed, on randomly generated instances inspired by computational results for the knapsack problem.

关键词： Stochastic programming Knapsack problem Pseudo-polynomial algorithm Mixed-integer non-linear programming branch-and-cut algorithm

来源：评论

学校读者我要写书评

暂无评论

Polyhedral study of simple plant location problem with order

引用

OPERATIONS RESEARCH LETTERS 2013年第2期41卷 153-158页

作者： Vasilyev, Igor Klimentova, Xenia Boccia, Maurizio Russian Acad Sci ISDCT SB RAS Inst Syst Dynam & Control Theory Siberian Branch Irkutsk 664033 Russia Univ Sannio Dipartimento Ingn I-82100 Benevento Italy

This paper is addressed to the generalization of simple plant location problem where customer's preferences are taken into account. Some basic polyhedral studies and a new family of facet-defining inequalities are given. The effectiveness of the proposed approach is illustrated by the computational experience. (c) 2012 Elsevier B.V. All rights reserved.

关键词： Simple plant location problem with order Facet-defining inequality branch-and-cut algorithm

来源：评论

学校读者我要写书评

暂无评论

A MIXED INTEGER LINEAR PROGRAMMING FORMULATION FOR THE SPARSE RECOVERY PROBLEM IN COMPRESSED SENSING

A MIXED INTEGER LINEAR PROGRAMMING FORMULATION FOR THE SPARS...

引用

IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP)

作者： Karahanoglu, N. Burak Erdogan, Hakan Birbil, S. Ilker TUBITAK BILGEM Adv Technol Res Inst Kocaeli Turkey Sabanci Univ Fac Engn & Nat Sci Istanbul Turkey

ISBN: (纸本)9781479903566

We propose a new mixed integer linear programming (MILP) formulation of the sparse signal recovery problem in compressed sensing (CS). This formulation is obtained by introduction of an auxiliary binary vector, where ones locate the recovered nonzero indices. Joint optimization for finding this auxiliary vector together with the underlying sparse vector leads to the proposed MILP formulation. By addition of a few appropriate constraints, this problem can be solved by existing MILP solvers. In contrast to other methods, this formulation is not an approximation of the sparse optimization problem, but is its equivalent. Hence, its solution is exactly equal to the optimal solution of the original sparse recovery problem, once it is feasible. We demonstrate this by recovery simulations involving different sparse signal types. The proposed scheme improves recovery over the mainstream CS recovery methods especially when the underlying sparse signals have constant amplitude nonzero elements.

关键词： compressed sensing l(0) norm minimization sparse signal recovery mixed integer linear programming branch-and-cut algorithm

来源：评论

学校读者我要写书评

暂无评论

Separating valid odd-cycle and odd-set inequalities for the multiple depot vehicle scheduling problem

引用

EURO JOURNAL ON COMPUTATIONAL OPTIMIZATION 2013年第3-4期1卷 283-312页

作者： Groiez, Mounira Desaulniers, Guy Hadjar, Ahmed Marcotte, Odile Ecole Polytechn Montreal Dept Math & Genie Ind Montreal PQ H3C 3A7 Canada Gerad Montreal PQ H3C 3A7 Canada Kronos Canadian Syst Inc Montreal PQ H3V 1H8 Canada Univ Quebec Montreal Dept Informat CP 8888Succ Ctr Ville Montreal PQ H3C 3P8 Canada Gerad Montreal PQ H3C 3P8 Canada

We consider the multicommodity network flow formulation of the multiple depot vehicle scheduling problem (MDVSP) and investigate several strategies within a branch-and-cut framework for solving the MDVSP. In particular, we compare sub-algorithms for separating the cutting planes introduced by Hadjar et al. (Oper Res 54:130-149, 2006). We also evaluate the effectiveness of a new criterion for fixing some variables in the multicommodity flow formulation. Finally, we present computational experiments to illustrate the strengths and weaknesses of the strategies.

关键词： Transportation scheduling Multicommodity flow branch-and-cut algorithm

来源：评论

学校读者我要写书评

暂无评论

Solving VLSI design and DNA sequencing problems using bipartization of graphs

引用

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS 2012年第2期51卷 749-781页

作者： Fouilhoux, Pierre Mahjoub, A. Ridha Univ Paris 09 LAMSADE CNRS F-75775 Paris 16 France Univ Paris 06 Lab LIP6 CNRS UMR 7626 F-75005 Paris France

In this paper we consider the 2-layer constrained via minimization problem and the SNP haplotype assembly problem. The former problem arises in the design of integrated and printed circuit boards, and the latter comes up in the DNA sequencing process for diploid organisms. We show that, for any maximum junction degree, the problem can be reduced to the maximum bipartite induced subgraph problem. Moreover we show that the SNP haplotype assembly problem can also be reduced to the maximum bipartite induced subgraph problem for the so-called minimum error correction criterion. We give a partial characterization of the bipartite induced subgraph polytope. Using this, we devise a branch-and-cut algorithm and report some experimental results. This algorithm has been used to solve real and large instances.

关键词： Electronics Genomics Bipartite induced subgraph problem Polyhedral approach branch-and-cut algorithm

来源：评论

学校读者我要写书评

暂无评论

Exact algorithms for Cluster Editing: Evaluation and Experiments

引用

algorithmICA 2011年第2期60卷 316-334页

作者： Boecker, Sebastian Briesemeister, Sebastian Klau, Gunnar W. Univ Jena Inst Informat Jena Germany Jena Ctr Bioinformat Jena Germany Univ Tubingen Div Simulat Biol Syst ZBIT WSI Tubingen Germany CWI NL-1090 GB Amsterdam Netherlands

The Cluster Editing problem is defined as follows: Given an undirected, loopless graph, we want to find a set of edge modifications (insertions and deletions) of minimum cardinality, such that the modified graph consists of disjoint cliques. We present empirical results for this problem using exact methods from fixed-parameter algorithmics and linear programming. We investigate parameter-independent data reduction methods and find that effective preprocessing is possible if the number of edge modifications k is smaller than some multiple of vertical bar V vertical bar , where V is the vertex set of the input graph. In particular, combining parameter-dependent data reduction with lower and upper bounds we can effectively reduce graphs satisfying k <= 25 vertical bar V vertical bar In addition to the fastest known fixed-parameter branching strategy for the problem, we investigate an integer linear program (ILP) formulation of the problem using a cutting plane approach. Our results indicate that both approaches are capable of solving large graphs with 1000 vertices and several thousand edge modifications. For the first time, complex and very large graphs such as biological instances allow for an exact solution, using a combination of the above techniques. (A preliminary version of this paper appeared under the title "Exact algorithms for cluster editing: Evaluation and experiments" in the Proceedings of the 7th Workshop on Experimental algorithms, WEA 2008, in: LNCS, vol. 5038, Springer, pp. 289-302.).

关键词： Cluster editing algorithm engineering Computer experiments NP-complete problem Fixed-parameter tractability FPT Integer linear programming ILP branch-and-cut algorithm

来源：评论

学校读者我要写书评

暂无评论

Combinatorial optimization model and MIP formulation for the structural analysis of conditional differential-algebraic systems

引用

COMPUTERS & INDUSTRIAL ENGINEERING 2011年第2期61卷 422-429页

作者： Lacroix, Mathieu Mahjoub, A. Ridha Martin, Sebastien Univ Paris 09 LAMSADE F-75775 Paris 16 France Univ Blaise Pascal Clermont Ferrand II LIMOS F-63177 Aubiere France

In this paper we consider the structural analysis problem for differential-algebraic systems with conditional equations. This problem consists, given a conditional differential-algebraic system, in verifying if the system is structurally nonsingular for every state, and if not in finding a state in which the system is structurally singular. We give a formulation for this problem as an integer linear program. This is based on a transformation of the problem into a matching problem in an auxiliary graph. We also show that the linear relaxation of that formulation can be solved in polynomial time. using this, we develop a branch-and-cut algorithm for solving the problem and present some experimental results. (C) 2011 Elsevier Ltd. All rights reserved.

关键词： Differential-algebraic system Structural analysis Graph Integer linear program Matching branch-and-cut algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：