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

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

The submodular knapsack polytope

引用

DISCRETE OPTIMIZATION 2009年第4期6卷 333-344页

作者： Atamtuerk, Alper Narayanan, Vishnu Univ Calif Berkeley Dept Ind Engn & Operat Res Berkeley CA 94720 USA Indian Inst Technol Mumbai 400076 Maharashtra India

The submodular knapsack set is the discrete lower level set of a submodular function. The modular case reduces to the classical linear 0-1 knapsack set. One motivation for studying the submodular knapsack polytope is to address 0-1 programming problems with uncertain coefficients. Under various assumptions, a probabilistic constraint on 0-1 variables can be modeled as a submodular knapsack set. In this paper we describe cover inequalities for the submodular knapsack set and investigate their lifting problem. Each lifting problem is itself an optimization problem over a submodular knapsack set. We give sequence-independent upper and lower bounds on the valid lifting coefficients and show that whereas the upper bound can be computed in polynomial time, the lower bound problem is NP-hard. Furthermore, we present polynomial algorithms based on parametric linear programming and computational results for the conic quadratic 0-1 knapsack case. (C) 2009 Elsevier B.V. All rights reserved.

关键词： Conic integer programming Submodular functions Probabilistic knapsacks branch-and-cut algorithms

来源：评论

学校读者我要写书评

暂无评论

On the hop-constrained survivable network design problem with reliable edges

引用

COMPUTERS & OPERATIONS RESEARCH 2015年第Dec.期64卷 159-167页

作者： Botton, Quentin Fortz, Bernard Gouveia, Luis Catholic Univ Louvain Louvain Sch Management Louvain Belgium Univ Libre Bruxelles Fac Sci Dept Informat Brussels Belgium Univ Lisbon Fac Ciencias DEIO CIO Lisbon Portugal

In this paper, we study the hop-constrained survivable network design problem with reliable edges. Given a graph with non-negative edge costs and node pairs Q the hop-constrained survivable network design problem consists of constructing a minimum cost 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. In addition, we consider here a subset of reliable edges that are not subject to failure. We study two variants: a static problem where the reliability of edges is given, and an upgrading problem where edges can be upgraded to the reliable status at a given cost We adapt for the two variants an extended formulation proposed in Botton, Fortz, Gouveia, Poss (2011) [1] for the case without reliable edges. As before, we use Benders decomposition to accelerate the solving process. Our computational results indicate that these two variants appear to be more difficult to solve than the original problem (without reliable edges). We conclude with an economical analysis which evaluates the incentive of using reliable edges in the network. (C) 2015 Elsevier Ltd. All rights reserved.

关键词： Network design Survivability Hop constraints Benders decomposition branch-and-cut algorithms

来源：评论

学校读者我要写书评

暂无评论

Some formulations for the group steiner tree problem

引用

DISCRETE APPLIED MATHEMATICS 2006年第13期154卷 1877-1884页

作者： Ferreira, Carlos E. de Oliveira Filho, Fernando M. Univ Sao Paulo Inst Math & Stat Dept Comp Sci Sao Paulo Brazil

The group Steiner tree problem consists of, given a graph G, a collection M of subsets of V (G) and a cost c(e) for each edge of G, finding a minimum-cost subtree that connects at least one vertex from each R is an element of R. It is a generalization of the well-known Steiner tree problem that arises naturally in the design of VLSI chips. In this paper, we study a polyhedron associated with this problem and some extended formulations. We give facet defining inequalities and explore the relationship between the group Steiner tree problem and other combinatorial optimization problems. (c) 2006 Elsevier B.V. All rights reserved.

关键词： combinatorial optimization polyhedral combinatorics integer programming formulations branch-and-cut algorithms

来源：评论

学校读者我要写书评

暂无评论

Conic mixed-integer rounding cuts

引用

MATHEMATICAL PROGRAMMING 2010年第1期122卷 1-20页

作者： Atamtuerk, Alper Narayanan, Vishnu Univ Calif Berkeley Dept Ind Engn & Operat Res Berkeley CA 94720 USA

A conic integer program is an integer programming problem with conic constraints. Many problems in finance, engineering, statistical learning, and probabilistic optimization are modeled using conic constraints. Here we study mixed-integer sets defined by second-order conic constraints. We introduce general-purpose cuts for conic mixed-integer programming based on polyhedral conic substructures of second-order conic sets. These cuts can be readily incorporated in branch-and-bound algorithms that solve either second-order conic programming or linear programming relaxations of conic integer programs at the nodes of the branch-and-bound tree. Central to our approach is a reformulation of the second-order conic constraints with polyhedral second-order conic constraints in a higher dimensional space. In this representation the cuts we develop are linear, even though they are nonlinear in the original space of variables. This feature leads to a computationally efficient implementation of nonlinear cuts for conic mixed-integer programming. The reformulation also allows the use of polyhedral methods for conic integer programming. We report computational results on solving unstructured second-order conic mixed-integer problems as well as mean-variance capital budgeting problems and least-squares estimation problems with binary inputs. Our computational experiments show that conic mixed-integer rounding cuts are very effective in reducing the integrality gap of continuous relaxations of conic mixed-integer programs and, hence, improving their solvability.

关键词： Conic programming Integer programming Mixed-integer rounding 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

来源：评论

学校读者我要写书评

暂无评论

A polyhedral approach to the asymmetric traveling salesman problem

引用

MANAGEMENT SCIENCE 1997年第11期43卷 1520-1536页

作者： Fischetti, M Toth, P UNIV BOLOGNA DEISBOLOGNAITALY

Several branch-and-bound algorithms for the exact solution of the asymmetric traveling salesman problem (ATSP), based on the assignment problem (AP) relaxation, have been proposed in the literature. These algorithms perform very well for some instances (e.g., those with uniformly random integer costs), but very poorly for others. The aim of this paper is to evaluate the effectiveness of a branch-and-cut algorithm exploiting ATSP-specific facet-defining cuts, to be used to attack hard instances that cannot be solved by the AP-based procedures from the literature. We present new separation algorithms for some classes of facet-defining cuts, and a new variable-pricing technique for dealing with highly degenerate primal LP problems. A branch-and-cut algorithm based on these new results is designed and evaluated through computational analysis on several classes of both random and real-world instances. The outcome of the research is that, on hard instances, the branch-and-cut algorithm clearly outperforms the best AP-based algorithms from the literature.

关键词： traveling salesman problem branch-and-cut algorithms separation computational analysis

来源：评论

学校读者我要写书评

暂无评论

A new formulation for the Traveling Deliveryman Problem

引用

DISCRETE APPLIED MATHEMATICS 2008年第17期156卷 3223-3237页

作者： Mendez-Diaz, Isabel Zabala, Paula Lucena, Abilio Univ Buenos Aires FCEyN Depto Computac RA-1053 Buenos Aires DF Argentina Univ Fed Rio de Janeiro Depto Adm BR-21941 Rio De Janeiro Brazil

The Traveling Deliveryman Problem is a generalization of the Minimum Cost Hamiltonian Path Problem where the starting vertex of the path, i.e. a depot vertex, is fixed in advance and the cost associated with a Hamiltonian path equals the sum of the costs for the layers of paths (along the Hamiltonian path) going from the depot vertex to each of the remaining vertices. In this paper, we propose a new Integer Programming formulation for the problem and computationally evaluate the strength of its Linear Programming relaxation. Computational results are also presented for a cutting plane algorithm that uses a number of valid inequalities associated with the proposed formulation. Some of these inequalities are shown to be facet defining for the convex hull of feasible solutions to that formulation. These inequalities proved very effective when used to reinforce Linear Programming relaxation bounds, at the nodes of a branch and Bound enumeration tree. (C) 2008 Elsevier B.V. All rights reserved.

关键词： Traveling deliveryman problem Integer programming branch-and-cut algorithms

来源：评论

学校读者我要写书评

暂无评论

Intermediate integer programming representations using value disjunctions

引用

DISCRETE OPTIMIZATION 2008年第2期5卷 293-313页

作者： Koeppe, Matthias Louveaux, Quentin Weismantel, Robert Otto VonGuericke Univ Magdeburg Dept Math IMO D-39106 Magdeburg Germany

We introduce a general technique for creating an extended formulation of a mixed-integer program. We classify the integer variables into blocks, each of which generates a finite set of vector values. The extended formulation is constructed by creating a new binary variable for each generated value. Initial experiments show that the extended formulation can have a more compact complete description than the original formulation. We prove that, using this reformulation technique, the facet description decomposes into one "linking polyhedron" per block and the "aggregated polyhedron". Each of these polyhedra can be analyzed separately. For the case of identical coefficients in a block, we provide a complete description of the linking polyhedron and a polynomial-time separation algorithm. Applied to the knapsack with a fixed number of distinct coefficients, this theorem provides a complete description in an extended space with a polynomial number of variables. On the basis of this theory, we propose a new branching scheme that analyzes the problem structure. It is designed to be applied in those subproblems of hard integer programs where LP-based techniques do not provide good branching decisions. Preliminary computational experiments show that it is successful for some benchmark problems of multi-knapsack type. (c) 2007 Elsevier B.V. All rights reserved.

关键词： mixed-integer programming extended formulations branch-and-cut algorithms polyhedral combinatorics

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：