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

integer programming formulations for the k-edge-connected 3-hop-constrained network design problem

NETWORKS 2016年第2期67卷 148-169页

作者： Diarrassouba, I. Gabrel, V. Mahjoub, A. R. Gouveia, L. Pesneau, P. Univ Havre Lab LMAH 25 Rue Philippe Lebon F-76600 Le Havre France Univ Paris 09 Lab LAMSADE Pl Marechal Lattre Tassigny F-75775 Paris 16 France Univ Lisbon Fac Ciencias Ctr Invest Operac Dept Estat & Invest Operac P-1699 Lisbon Portugal Univ Bordeaux INRIA Bordeaux Sud Ouest IMB UMR 5251 Bordeaux France

In this article, we study the k-edge-connected L-hop-constrained network design problem. Given a weighted graph , a set D of pairs of nodes, two integers and , the problem consists in finding a minimum weight subgraph of G containing at least k edge-disjoint paths of length at most L between every pair . We consider the problem in the case where L=2, 3 and . We first discuss integer programming formulations introduced in the literature. Then, we introduce new integer programming formulations for the problem that are based on the transformation of the initial undirected graph into directed layered graphs. We present a theoretical comparison of these formulations in terms of LP-bound. Finally, these formulations are tested using CPLEX and compared in a computational study for k=3, 4, 5. (c) 2015 Wiley Periodicals, Inc. NETWORKS, 67(2), 148-169 2016

关键词： survivable network edge-disjoint paths flow hop-constrained path integer programming formulation k-edge-connected aggregated formulations separated formulations

来源：评论

学校读者我要写书评

暂无评论

integer programming formulations for the two 4-hop-constrained paths problem

引用

NETWORKS 2007年第2期49卷 135-144页

作者： Huygens, David Mahjoub, A. Ridha Univ Clermont Ferrand LIMOS CNRS UMR 6158 F-63177 Clermont Ferrand France Free Univ Brussels Dept Informat B-1050 Brussels Belgium

In this article, we consider the two 4-hop-constrained paths problem, which consists, given a graph G = (N, E) and two nodes s, t is an element of N, of finding a minimum cost sub-graph in G containing at least two node- (resp., edge-) disjoint paths of length at most 4 between s and t. We give integer programming formulations, in the space of the design variables, for both the node and edge versions of this problem. (c) 2006 Wiley Periodicals, Inc.

关键词： survivable network edge-disjoint paths node-disjoint paths hop-constraint integer programming formulation

来源：评论

学校读者我要写书评

暂无评论

integer programming-based method for grammar-based tree compression and its application to pattern extraction of glycan tree structures

引用

BMC BIOINFORMATICS 2010年第s11期11卷 1-11页

作者： Zhao, Yang Hayashida, Morihiro Akutsu, Tatsuya Kyoto Univ Bioinformat Ctr Inst Chem Res Kyoto 6110011 Japan

Background: A bisection-type algorithm for the grammar-based compression of tree-structured data has been proposed recently. In this framework, an elementary ordered-tree grammar (EOTG) and an elementary unordered-tree grammar (EUTG) were defined, and an approximation algorithm was proposed. Results: In this paper, we propose an integer programming-based method that finds the minimum context-free grammar (CFG) for a given string under the condition that at most two symbols appear on the right-hand side of each production rule. Next, we extend this method to find the minimum EOTG and EUTG grammars for given ordered and unordered trees, respectively. Then, we conduct computational experiments for the ordered and unordered artificial trees. Finally, we apply our methods to pattern extraction of glycan tree structures. Conclusions: We propose integer programming-based methods that find the minimum CFG, EOTG, and EUTG for given strings, ordered and unordered trees. Our proposed methods for trees are useful for extracting patterns of glycan tree structures.

关键词： integer programming Production Rule Sibling Relationship integer programming formulation Terminal Symbol

来源：评论

学校读者我要写书评

暂无评论

Exact solution approaches for the discrete a-neighbor p-center problem

引用

NETWORKS 2023年第4期82卷 371-399页

作者： Gaar, Elisabeth Sinnl, Markus Johannes Kepler Univ Linz Inst Prod & Logist Management Linz Austria Johannes Kepler Univ Linz JKU Business Sch Linz Austria

The discrete a-neighbor p-center problem (d-a-pCP) is an emerging variant of the classical p-center problem which recently got attention in literature. In this problem, we are given a discrete set of points and we need to locate p facilities on these points in such a way that the maximum distance between each point where no facility is located and its a-closest facility is minimized. The only existing algorithms in literature for solving the d-a-pCP are approximation algorithms and two recently proposed heuristics. In this work, we present two integer programming formulations for the d-a-pCP, together with lifting of inequalities, valid inequalities, inequalities that do not change the optimal objective function value and variable fixing procedures. We provide theoretical results on the strength of the formulations and convergence results for the lower bounds obtained after applying the lifting procedures or the variable fixing procedures in an iterative fashion. Based on our formulations and theoretical results, we develop branch-and-cut (B&C ) algorithms, which are further enhanced with a starting heuristic and a primal heuristic. We evaluate the effectiveness of our B&C algorithms using instances from literature. Our algorithms are able to solve 116 out of 194 instances from literature to proven optimality, with a runtime of under a minute for most of them. By doing so, we also provide improved solution values for 116 instances.

关键词： integer programming formulation location science min-max objective p-center problem

来源：评论

学校读者我要写书评

暂无评论

A branch-and-cut algorithm for the restricted Block Relocation Problem

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2020年第2期287卷 452-459页

作者： Bacci, Tiziano Mattia, Sara Ventura, Paolo CNR Ist Anal Sistemi & Informat Via Taurini 19 I-00185 Rome Italy

We consider the Block Relocation Problem, that has a crucial role in the logistics of containers. It consists of minimizing the number of container relocations within a container bay/yard. Since the number of containers shipped worldwide grew dramatically in the last years, the problem has been widely investigated. Here we propose an exact algorithm for the restricted version of the Block Relocation Problem, based on a new integer linear programming formulation. We compare such new approach with the state-of-art exact methods. The computational results prove its effectiveness and show that it outperforms all the previously proposed procedures, in almost all the considered instances. (C) 2020 Elsevier B.V. All rights reserved.

关键词： Block Relocation problem integer programming formulation Branch-and-cut

来源：评论

学校读者我要写书评

暂无评论

A decomposition algorithm for the ring spur assignment problem

引用

INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH 2013年第1期20卷 119-139页

作者： Carroll, Paula McGarraghy, Sean Univ Coll Dublin Quinn Sch Business Ctr Business Analyt Dublin 4 Ireland

This paper describes the ring spur assignment problem (RSAP), a new problem arising in the design of next generation networks. The RSAP complements the sonet ring assignment problem (SRAP). We describe the RSAP, positioning it in relation to problems previously addressed in the literature. We decompose the problem into two IP problems and describe a branch-and-cut decomposition heuristic algorithm suitable for solving problem instances in a reasonable time. We present promising computational results.

关键词： networks graphs applications combinatorics integer programming formulation telecommunications network topology design cutting plane algorithm

来源：评论

学校读者我要写书评

暂无评论

Linear programming based meta-heuristics for the weighted maximal planar graph

引用

JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY 2002年第10期53卷 1142-1149页

作者： Osman, IH Hasan, M Abdullah, A Amer Univ Beirut Sch Business Beirut 11072020 Lebanon Kuwait Univ Safat Kuwait Univ Kent Canterbury Kent England

The weighted maximal planar graph (WMPG) is practically important in the laying out of facilities in modern manufacturing environments. Given a weighted complete graph, the WMPG seeks to find a sub-graph such that it isplanar—it can be embedded on the plane without any arcs intersecting, and it ismaximal—no additional arc can be added to the sub-graph without destroying its planarity, and it also has the maximal sum of arc weights. In this paper, an integer linear programming (ILP) model is newly introduced for the problem. Two meta-heuristics are then derived from the ILP relaxation. The first meta-heuristic considers all variables with fractional values greater than half in the ILP relaxation to build an initial sub-graph from which a planar sub-graph is extracted using greedy random adaptive search procedure (GRASP) and augmented by triangulation of faces. The second meta-heuristic considers only arcs with integer values in the ILP relaxation. The remaining arcs are then sorted in descending order of their weights, for selection and insertion with a planarity testing procedure, to obtain a feasible solution using GRASP. Computational results are reported on a set of 100 test instances of size varying from 20 to 100 facilities. The computational results demonstrate the tightness of the new upper bound when compared to the classical one as well as the good performance of the proposed metaheuristics when compared to the best-known procedures in the literature in terms of solution quality and computational requirement. Finally, the paper presents a successful integration of GRASP with classical optimisation approaches and should be attempted for other optimisation problems.

关键词： facility layout heuristics greedy adaptive random search procedure integer programming formulation maximal planar graph models meta-heuristics

来源：评论

学校读者我要写书评

暂无评论

Prediction of RNA secondary structure with pseudoknots using integer programming

引用

BMC BIOINFORMATICS 2009年第Sup1期10卷 1-11页

作者： Poolsap, Unyanee Kato, Yuki Akutsu, Tatsuya Kyoto Univ Inst Chem Res Bioinformat Ctr Kyoto 6110011 Japan

Background: RNA secondary structure prediction is one major task in bioinformatics, and various computational methods have been proposed so far. Pseudoknot is one of the typical substructures appearing in several RNAs, and plays an important role in some biological processes. Prediction of RNA secondary structure with pseudoknots is still challenging since the problem is NP-hard when arbitrary pseudoknots are taken into consideration. Results: We introduce a new method of predicting RNA secondary structure with pseudoknots based on integer programming. In our formulation, we aim at minimizing the value of the objective function that reflects free energy of a folding structure of an input RNA sequence. We focus on a practical class of pseudoknots by setting constraints appropriately. Experimental results for a set of real RNA sequences show that our proposed method outperforms several existing methods in sensitivity. Furthermore, for a set of sequences of small length, our approach achieved good performance in both sensitivity and specificity. Conclusion: Our integer programming-based approach for RNA structure prediction is flexible and extensible.

关键词： integer programming integer programming Problem integer programming formulation Pseudoknotted Structure Grammatical Approach

来源：评论

学校读者我要写书评

暂无评论

An efficient benders decomposition for the p-median problem

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2023年第1期308卷 84-96页

作者： Duran-Mateluna, Cristian Ales, Zacharie Elloumi, Sourour Inst Polytech Paris UMA ENSTA Paris F-91120 Palaiseau France CEDRIC Conservatoire Natl Arts & Metiers F-75003 Paris France Univ Santiago Chile Ind Engn Dept PDSPS Santiago 9160000 Chile

The p-median problem is a classic discrete location problem with numerous applications. It aims to open p sites while minimizing the sum of the distances of each client to its nearest open site. We study a Benders decomposition of the most efficient formulation in the literature. We show that the Benders cuts can be separated in linear time. The Benders reformulation leads to a compact formulation for the p-median problem. We implement a two-phase Benders decomposition algorithm that outperforms state-of-the-art methods on benchmark instances by an order of magnitude and allows to exactly solve for the first time several instances among which are large TSP instances and BIRCH instances. We also show that our implementation easily applies to the uncapacitated facility location problem.(c) 2022 Elsevier B.V. All rights reserved.

关键词： Location p-Median problem Benders decomposition integer programming formulation Polynomial separation algorithm

来源：评论

学校读者我要写书评

暂无评论

Single-machine scheduling with precedence constraints

引用

MATHEMATICS OF OPERATIONS RESEARCH 2005年第4期30卷 1005-1021页

作者： Correa, JR Schulz, AS Univ Adolfo Ibanez Sch Business Santiago Chile MIT Alfred P Sloan Sch Management Cambridge MA 02139 USA

We discuss the problem of sequencing precedence-constrained jobs on a single machine to minimize the average weighted completion time. This problem has attracted much attention in the mathematical programming community since Sidney's pioneering work in 1975 (Sidney, J. B. 1975. Decomposition algorithms for single machine scheduling with precedence relations and deferral costs. Operations Research 23 283-298). We look at the problem from a polyhedral perspective and uncover a relation between Sidney's decomposition theorem and different linear programming relaxations. More specifically, we present a generalization of Sidney's result, which particularly allows us to reason that virtually all known 2-approximation algorithms are consistent with his decomposition. Moreover, we establish a connection between the single-machine scheduling problem and the vertex cover problem. Indeed, in the special case of series-parallel precedence constraints, we prove that the sequencing problem can be seen 'as a special case of the vertex cover problem. We also. argue that this result is true for general precedence constraints if one can show that a certain integer program represents a valid formulation of the sequencing problem. Finally, we give a 3/2-approximation algorithm for two-dimensional partial orders, and we also provide a characterization of the active inequalities of a linear programming relaxation in completion time variables.

关键词： linear ordering scheduling vertex cover linear programming relaxation integer programming formulation approximation algorithm partial order

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：