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

Improved formulations and branch-and-cut algorithms for the angular constrained minimum spanning tree problem

JOURNAL OF COMBINATORIAL OPTIMIZATION 2022年第1期44卷 379-413页

作者： da Cunha, Alexandre Salles Univ Fed Minas Gerais Dept Ciencia Comp Belo Horizonte MG Brazil

The Angular Constrained Minimum Spanning Tree Problem (alpha-MSTP) is defined in terms of a complete undirected graph G = (V, E) and an angle alpha is an element of (0, 2 pi]. Vertices of G define points in the Euclidean plane while edges, the line segments connecting them, are weighted by the Euclidean distance between their endpoints. A spanning tree is an alpha-spanning tree (alpha-ST) of G if, for any i is an element of V, the smallest angle that encloses all line segments corresponding to its i-incident edges does not exceed a. alpha-MSTP consists in finding an alpha-ST with the least weight. In this work, we discuss families of alpha-MSTP valid inequalities. One of them is a lifting of existing angular constraints found in the literature and the others come from the Stable Set polytope, a structure behind alpha-STs disclosed here. We show that despite being already satisfied by the previously strongest known formulation, F-xy, these lifted angular constraints are capable of strengthening another existing alpha-MSTPmodel so that both become equally strong, at least for the instances tested here. Inequalities from the Stable Set polytope improve the best known Linear Programming Relaxation (LPRs) bounds by about 1.6%, on average, for the hardest instances of the problem. Additionally, we indicate howformulation F-xy can be more effectively used in branch-and-cut (BC) algorithms, by reducing the number of variables explicitly enforced to be integer constrained and by eliminating constraints that do not change the quality of its LPR bounds. Extensive computational experiments conducted here suggest that the combination of the ideas above allows us to redefine the best performing alpha-MSTP algorithms, for almost the entire spectrum of a values, the exception being the easy instances, thosewith alpha >= 2 pi/3. In particular, for the hardest ones (corresponding to alpha is an element of {pi/2, pi/3, 2 pi/5}) that could be solved to proven optimality, the bestBCalgo

关键词： Combinatorial optimization Angular constrained spanning trees Stable set polytope branch-and-cut algorithms

来源：评论

学校读者我要写书评

暂无评论

Stable set reformulations for the degree preserving spanning tree problem

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2024年第1期319卷 50-61页

作者： Lucena, Abilio da Cunha, Alexandre Salles Univ Fed Rio De Janeiro Programa Engn Sistemas & Computacao Rio De Janeiro Brazil Univ Fed Minas Gerais Dept Ciencia Computacao Belo Horizonte Brazil

Let G = ( V, E) ) be a connected undirected graph and assume that a spanning tree is available for it. Any vertex in this tree is called degree preserving if it has the same degree in the graph and in the tree. Building upon this concept, the Degree Preserving Spanning Tree Problem (DPSTP) asks for a spanning tree of G with as many degree preserving vertices as possible. DPSTP is very much intertwined with the most important application for it, so far, i.e., the online monitoring of arc flows in a water distribution network, what serves us as an additional motivation for our investigation. We show that degree preserving vertices correspond to a stable set of a properly defined DPSTP conflict graph. This, in turn, allows us to use valid inequalities for the Stable Set Polytope (SSP) and thus strengthen the DPSTP formulations previously suggested in the literature. In doing so, the branch-and-cut and Benders Decomposition algorithms suggested for these formulations are greatly enhanced. Additionally, as a further contribution, we also introduce a new and very challenging set of DPSTP test instances, given by graphs that closely resemble water distribution networks. For these instances, the new algorithms very clearly outperform all previous DPSTP algorithms. They not only run faster than their competitors but are also less dependent on good initial DPSTP primal bounds. For previous DPSTP test sets, the new algorithms lag behind the best existing algorithm for them, which is based on Lagrangian relaxation. However, as compared to additional DPSTP previous algorithms that do not benefit from SSP inequalities, the new ones come much closer to the Lagrangian relaxation one.

关键词： Combinatorial optimization Degree preserving spanning trees Stable set branch-and-cut algorithms Combinatorial benders decomposition

来源：评论

学校读者我要写书评

暂无评论

Valid inequalities and a branch-and-cut algorithm for the routing and spectrum allocation problem 11

Valid inequalities and a branch-and-cut algorithm for the ro...

引用

11th Latin and American algorithms, Graphs and Optimization Symposium (LAGOS)

作者： Bianchetti, Marcelo Marenco, Javier Univ Buenos Aires FCEyN Dept Computat Buenos Aires DF Argentina Univ Nacl Gen Sarmiento Inst Ciencias Buenos Aires DF Argentina

One of the most promising solutions to deal with huge data traffic demands in large communication networks is given by flexible optical networking, in particular theflexible grid (flexgrid) technology specified in the ITU-T standard G.694.1. In this specification, the frequency spectrum of an optical fiber link is divided into narrow frequency slots. Any sequence of consecutive slots can be used as a simple channel, and such a channel can be switched in the network nodes to create a lightpath. In this kind of networks, the problem of establishing lightpaths for a set of end-to-end demands that compete for spectrum resources is called the routing and spectrum allocation problem (RSA). Due to its relevance, RSA has been intensively studied in the last years. It has been shown to be NP-hard and different solution approaches have been proposed for this problem. In this paper we present several families of valid inequalities, valid equations, and optimality cuts for a natural integer programming formulation of RSA and, based on these results, we develop a branch-and-cut algorithm for this problem. Our computational experiments suggest that such an approach is effective at tackling this problem. (C) 2021 The Authors. Published by Elsevier B.V.

关键词： integer programming branch-and-cut algorithms routing and spectrum allocation

来源：评论

学校读者我要写书评

暂无评论

A branch-and-cut algorithm for Mixed-Integer Bilinear Programming

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2020年第2期282卷 506-514页

作者： Fischetti, Matteo Monaci, Michele Univ Padua DEI Via Gradenigo 6-A I-35100 Padua Italy Univ Bologna DEI Guglielmo Marconi Viale Risorgimento 2 I-40136 Bologna Italy

In this paper, we consider the Mixed-Integer Bilinear Programming problem, a widely-used reformulation of the classical mixed-integer quadratic programming problem. For this problem we describe a branch and -cut algorithm for its exact solution, based on a new family of intersection cuts derived from bilinearspecific disjunctions. We also introduce a new branching rule that is specifically designed for bilinear problems. We computationally analyze the behavior of the proposed algorithm on a large set of mixed-integer quadratic instances from the MINLPIib problem library. Our results show that our method, even without intersection cuts, is competitive with a state-of-the-art mixed-integer nonlinear solver. As to intersection cuts, their extensive use at each branching node tends to slow down the solver for most problems in our test bed, but they are extremely effective for some specific instances. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Combinatorial optimization Mixed-integer quadratic programming Bilinear programming branch-and-cut algorithms Intersection cuts

来源：评论

学校读者我要写书评

暂无评论

Polyhedral results, branch-and-cut and Lagrangian relaxation algorithms for the adjacent only quadratic minimum spanning tree problem

引用

NETWORKS 2018年第1期71卷 31-50页

作者： Pereira, Dilson Lucas da Cunha, Alexandre Salles Univ Fed Lavras Dept Ciencia Comp Lavras Brazil Univ Fed Minas Gerais Dept Ciencia Comp Belo Horizonte MG Brazil

Given a complete and undirected graph G, the adjacent only quadratic minimum spanning tree problem (AQMSTP) consists of finding a spanning tree that minimizes a quadratic function of its adjacent edges. The strongest AQMSTP linear integer programming formulation in the literature works on an extended variable space, using exponentially many decision variables assigned to the stars of G. In this article, we characterize three families of facet defining inequalities by investigating the projection of that formulation onto the space of the canonical linearization variables. On the algorithmic side, we introduce four new branch-and-bound algorithms. Three of them are branch-and-cut algorithms based on the inequalities characterized by projection. The fourth is based on a Lagrangian relaxation scheme, also devised for the star reformulation. Two of the branch-and-cut algorithms provide very good results, almost always dominating the previously best algorithm for the problem. The Lagrangian relaxation based branch-and-bound algorithm provides even better results. It manages to solve all previously solved AQMSTP instances in the literature in about one tenth of the time needed by its competitors. (c) 2017 Wiley Periodicals, Inc. NETWORKS, Vol. 71(1), 31-50 2018

关键词： adjacent only quadratic minimum spanning tree problem projection branch-and-cut algorithms Lagrangian relaxation

来源：评论

学校读者我要写书评

暂无评论

Exact Solution algorithms for the Chordless Cycle Problem

引用

INFORMS JOURNAL ON COMPUTING 2022年第4期34卷 1970-1986页

作者： Pereira, Dilson Lucas Lucena, Abilio da Cunha, Alexandre Salles Simonetti, Luidi Univ Fed Lavras Dept Comp Aplicada Caixa 3037 BR-37200900 Caixa Brazil Univ Fed Rio de Janeiro Programa Engn Sistemas & Comp Caixa 68511 BR-21941972 Rio De Janeiro Brazil Univ Fed Minas Gerais Dept Ciencia Comp BR-31270901 Belo Horizonte MG Brazil

A formulation, a heuristic, and branch-and-cut algorithms are investigated for the chordless cycle problem. This is the problem of finding a largest simple cycle for a given graph so that no edge between nonimmediately subsequent cycle vertices is contained in the graph. Leaving aside procedures based on complete enumeration, no previous exact solution algorithm appears to exist for the problem, which is relevant both in theoretical and practical terms. Extensive computational results are reported here for randomly generated graphs and for graphs originating from the literature. Under acceptable CPU times, certified optimal solutions are presented for graphs with as many as 100 vertices.

关键词： induced subgraphs chordless cycles branch-and-cut algorithms

来源：评论

学校读者我要写书评

暂无评论

Valid inequalities and a branch-and-cut algorithm for the routing and spectrum allocation problem

引用

Procedia Computer Science 2021年 195卷 523-531页

作者： Marcelo Bianchetti Javier Marenco Departamento de Computación FCEyN Universidad de Buenos Aires Buenos Aires Argentina Instituto de Ciencias Universidad Nacional de General Sarmiento Buenos Aires Argentina

One of the most promising solutions to deal with huge data traffic demands in large communication networks is given by flexible optical networking, in particular the flexible grid (flexgrid) technology specified in the ITU-T standard G.694.1. In this specification, the frequency spectrum of an optical fiber link is divided into narrow frequency slots. Any sequence of consecutive slots can be used as a simple channel, and such a channel can be switched in the network nodes to create a lightpath. In this kind of networks, the problem of establishing lightpaths for a set of end-to-end demands that compete for spectrum resources is called the routing and spectrum allocation problem (RSA). Due to its relevance, RSA has been intensively studied in the last years. It has been shown to be NP-hard and different solution approaches have been proposed for this problem. In this paper we present several families of valid inequalities, valid equations, and optimality cuts for a natural integer programming formulation of RSA and, based on these results, we develop a branch-and-cut algorithm for this problem. Our computational experiments suggest that such an approach is effective at tackling this problem.

关键词： integer programming branch-and-cut algorithms routing spectrum allocation

来源：评论

学校读者我要写书评

暂无评论

Benders decomposition for very large scale partial set covering and maximal covering location problems

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2019年第3期275卷 882-896页

作者： Cordeau, Jean-Francois Furini, Fabio Ljubic, Ivana HEC Montreal 3000 Chemin Cote St Catherine Montreal PQ H3T 2A7 Canada Univ Paris 09 PSL Res Univ CNRS LAMSADE F-75016 Paris France ESSEC Business Sch Paris 3 Av Bernard HirschBP 50105 F-95021 Cergy Pontoise France

Covering problems constitute a fundamental family of facility location problems. This paper introduces a new exact algorithm for two important members of this family: (i) the maximal covering location problem (MCLP), which requires finding a subset of facilities that maximizes the amount of customer demand covered while respecting a budget constraint on the cost of the facilities;and (ii) the partial set covering location problem (PSCLP), which minimizes the cost of the open facilities while forcing a certain amount of customer demand to be covered. We study an effective decomposition approach to the two problems based on the branch-and-Benders-cut reformulation. Our new approach is designed for the realistic case in which the number of customers is much larger than the number of potential facility locations. We report the results of a series of computational experiments demonstrating that, thanks to this decomposition techniques, optimal solutions can be found very quickly for some benchmark instances with one hundred potential facility locations and involving up to 15 and 40 million customer demand points for the MCLP and the PSCLP, respectively. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Combinatorial optimization Location problems Covering Benders decomposition branch-and-cut algorithms

来源：评论

学校读者我要写书评

暂无评论

Modeling and solving the angular constrained minimum spanning tree problem

引用

COMPUTERS & OPERATIONS RESEARCH 2019年 112卷 104775-000页

作者： da Cunha, Alexandre Salles Lucena, Abilio Univ Fed Minas Gerais Dept Ciencia Comp Belo Horizonte MG Brazil Univ Fed Rio de Janeiro Programa Engn Sistemas & Comp Rio De Janeiro Brazil

Assume one is given an angle alpha is an element of(0, 2 pi] and a complete undirected graph G = (V, E). The vertices in V represent points in the Euclidean plane. The edges in E represent the line segments between these points, with edge weights equal to segment lengths. Spanning trees of G are called alpha-spanning trees (alpha-STs) if, for any i is an element of V, the smallest angle that encloses all line segments corresponding to its i-incident edges does not exceed alpha. The Angular Constrained Minimum Spanning Tree Problem (alpha-MSTP) seeks an alpha-ST with the least weight. The problem arises in the design of wireless communication networks operating under directional antennas. We propose two alpha-MSTP formulations. One, F-x requiring, in principle, O(2(vertical bar V vertical bar)) inequalities to model the angular constraints (alpha-AC). For alpha is an element of(0, pi), however, we show that just O(vertical bar V vertical bar(3)) of them suffice to attain not only a formulation but also the same Linear Programming relaxation (LPR) bound as the full blown model. The other formulation, F-xy, enlarges the set of F-x variables but manages to model alpha-AC, compactly. Furthermore, F-xy LPR bounds are proven to dominate their F-x counterparts. That dominance, however, is empirically shown to reduce as alpha increases. Finally, exact branch-and-cut algorithms implemented for the two formulations are shown, empirically, to exchange roles as top performer, throughout the [0, 2 pi) range of alpha values. (C) 2019 Elsevier Ltd. All rights reserved.

关键词： Combinatorial optimization Angular constrained spanning trees branch-and-cut algorithms Polyhedral combinatorics

来源：评论

学校读者我要写书评

暂无评论

Contingency-Constrained Unit Commitment With Intervening Time for System Adjustments

引用

IEEE TRANSACTIONS ON POWER SYSTEMS 2017年第4期32卷 3049-3059页

作者： Guo, Zhaomiao Chen, Richard Li-Yang Fan, Neng Watson, Jean-Paul Argonne Natl Lab Div Energy Syst Lemont IL 60439 USA Sandia Natl Labs Quantitat Modeling & Anal Dept Livermore CA 94551 USA Univ Arizona Dept Syst & Ind Engn Tucson AZ 85721 USA Sandia Natl Labs Discrete Math & Optimizat Dept Albuquerque NM 87185 USA

The N-1-1 contingency reliability criterion considers the consecutive loss of two components in a power system, with intervening time for system adjustments between the two losses. In this paper, we consider the problem of optimizing generation unit while ensuring the N-1-1 criterion. Due to the coupling of time periods associated with consecutive component losses, the resulting problem yields a very large-scale mixed-integer linear optimization model. For efficient solution, we introduce a novel branch-and-cut algorithm using a temporally decomposed bilevel separation oracle. The model and algorithm are assessed using multiple IEEE test systems, and a comprehensive analysis is performed to compare system performance across different contingency criteria. Computational results demonstrate the value of considering intervening time for system adjustments in terms of total cost and system robustness.

关键词： Benders decomposition branch-and-cut algorithms contingency constraints non-simultaneous failures unit commitment

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：