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

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

New branch-and-cut algorithm for bilevel linear programming

引用

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS 2007年第2期134卷 353-370页

作者： Audet, C. Savard, G. Zghal, W. Ecole Hautes Etud Commerciales Gerad Montreal PQ Canada Ecole Polytech Montreal PQ H3C 3A7 Canada

Linear mixed 0-1 integer programming problems may be reformulated as equivalent continuous bilevel linear programming (BLP) problems. We exploit these equivalences to transpose the concept of mixed 0-1 Gomory cuts to BLP. The first phase of our new algorithm generates Gomory-like cuts. The second phase consists of a branch-and-bound procedure to ensure finite termination with a global optimal solution. Different features of the algorithm, in particular, the cut selection and branching criteria are studied in details. We propose also a set of algorithmic tests and procedures to improve the method. Finally, we illustrate the performance through numerical experiments. Our algorithm outperforms pure branch-and-bound when tested on a series of randomly generated problems.

关键词： Bilevel linear programming Gomory cuts linear mixed 0-1 integer programming branch-and-cut algorithms

来源：评论

学校读者我要写书评

暂无评论

A branch-and-cut algorithm for Graph Coloring

引用

DISCRETE APPLIED MATHEMATICS 2006年第5期154卷 826-847页

作者： Méndez-Díaz, I Zabala, P Univ Buenos Aires FCEyN Dept Computac RA-1053 Buenos Aires DF Argentina

In this paper a branch-and-cut algorithm, based on a formulation previously introduced by us, is proposed for the Graph Coloring Problem. Since colors are indistinguishable in graph coloring, there may typically exist many different symmetrical colorings associated with a same number of colors. If solutions to an integer programming model of the problem exhibit that property, the branch-and-cut method tends to behave poorly even for small size graph coloring instances. Our model avoids, to certain extent, that bottleneck. Computational experience indicates that the results we obtain improve, in most cases, on those given by the well-known exact solution graph coloring algorithm Dsatur. (c) 2005 Elsevier B.V. All rights reserved.

关键词： Graph Coloring integer programming branch-and-cut algorithms

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Generalized branch-and-cut framework for mixed-integer nonlinear optimization problems

引用

COMPUTERS & CHEMICAL ENGINEERING 2000年第2-7期24卷 1361-1366页

作者： Kesavan, P Barton, PI MIT Dept Chem Engn Cambridge MA 02139 USA

branch and bound (BB) is the primary deterministic approach that has been applied successfully to solve mixed-integer nonlinear programming (MINLPs) problems in which the participating functions are nonconvex. Recently, a decomposition algorithm was proposed to solve nonconvex MINLPs. In this work, a generalized branch and cut (GBC) algorithm is proposed and it is shown that both decomposition and BE algorithms are specific instances of the GBC algorithm with a certain set of heuristics. This provides a unified framework for comparing BE and decomposition algorithms. Finally, a set of heuristics which may be potentially more efficient computationally compared to all currently available deterministic algorithms is presented. (C) 2000 Elsevier Science Ltd. All rights reserved.

关键词： branch-and-cut algorithms mixed-integer nonlinear optimization decomposition heuristics

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Generalized branch-and-cut framework for mixed-integer nonlinear optimization problems

Generalized branch-and-cut framework for mixed-integer nonli...

引用

7th International Symposium on Process Systems Engineering

作者： Kesavan, P Barton, PI MIT Dept Chem Engn Cambridge MA 02139 USA

关键词： branch-and-cut algorithms mixed-integer nonlinear optimization decomposition heuristics

来源：评论

学校读者我要写书评

暂无评论

Solving the cell suppression problem on tabular data with linear constraints

引用

MANAGEMENT SCIENCE 2001年第7期47卷 1008-1027页

作者： Fischetti, M Salazar, JJ Univ Padua DEI Padua Italy Univ La Laguna DEIOC E-38207 La Laguna Spain

Cell suppression is a widely used technique for protecting sensitive information in statistical data presented in tabular form. Previous works on the subject mainly concentrate on 2- and 3-dimensional tables whose entries are subject to marginal totals. In this paper we address the problem of protecting sensitive data in a statistical table whose entries are linked by a generic system of linear constraints. This very general setting covers, among others, k-dimensional tables with marginals as well as the so-called hierarchical and linked tables that are very often used nowadays for disseminating statistical data. In particular, we address the optimization problem known in the literature as the (secondary) Cell Suppression Problem, in which the information loss due to suppression has to be minimized. We introduce a new integer linear programming model and outline an enumerative algorithm for its exact solution. The algorithm can also be used as a heuristic procedure to find near-optimal solutions. Extensive computational results on a test-bed of 1,160 real-world and randomly generated instances are presented, showing the effectiveness of the approach. In particular, we were able to solve to proven optimality 4-dimensional tables with marginals as well as linked tables of reasonable size (to our knowledge, tables of this kind were never solved optimally by previous authors).

关键词： statistical disclosure control confidentiality cell suppression integer linear programming tabular data branch-and-cut algorithms

来源：评论

学校读者我要写书评

暂无评论

Supermodular covering knapsack polytope

引用

DISCRETE OPTIMIZATION 2015年 18卷 74-86页

作者： Atamtuerk, Alper Bhardwaj, Avinash Univ Calif Berkeley Ind Engn & Operat Res Berkeley CA 94720 USA

The supermodular covering knapsack set is the discrete upper level set of a non-decreasing supermodular function. Submodular and supermodular knapsack sets arise naturally when modeling utilities, risk and probabilistic constraints on discrete variables. In a recent paper Atamturk and Narayanan (2009) study the lower level set of a non-decreasing submodular function. In this complementary paper we describe pack inequalities for the supermodular covering knapsack set and investigate their separation, extensions and lifting. We give sequence-independent upper bounds and lower bounds on the lifting coefficients. Furthermore, we present a computational study on using the polyhedral results derived for solving 0-1 optimization problems over conic quadratic constraints with a branch-and-cut algorithm. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Conic integer programming Supermodularity Lifting Probabilistic covering knapsack constraints branch-and-cut algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：