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

The mixed general routing polyhedron

MATHEMATICAL PROGRAMMING 2003年第1期96卷 103-137页

作者： Corberán, A Romero, A Sanchis, JM Univ Valencia Dept Estadist & Invest Operat E-46003 Valencia Spain Univ Politecn Valencia Dept Matemat Aplicada E-46071 Valencia Spain

In Arc Routing Problems, ARPs, the aim is to find on a graph a minimum cost traversal satisfying some conditions related to the links of the graph. Due to restrictions to traverse some streets in a specified way, most applications of ARPs must be modeled with a mixed graph. Although several exact algorithms have been proposed, no polyhedral investigations have been done for ARPs on a mixed graph. In this paper we deal with the Mixed General Routing Problem which consists of finding a minimum cost traversal of a given link subset and a given vertex subset of a mixed graph. A formulation is given that uses only one variable for each link (edge or arc) of the graph. Some properties of the associated polyhedron and some large families of facet-inducing inequalities are described. A preliminary cutting-plane algorithm has produced very good lower bounds over a set of 100 randomly generated instances of the Mixed Rural Postman Problem. Finally, applications of this study to other known routing problems are described.

关键词： polyhedral combinatorics facets routing Arc Routing Rural Postman Problem General Routing Problem Mixed Chinese Postman Problem

来源：评论

学校读者我要写书评

暂无评论

On the complexity of the separation problem for rounded capacity inequalities

引用

DISCRETE OPTIMIZATION 2017年 25卷 86-104页

作者： Diarrassouba, Ibrahima Normandie Univ UNIHAVRE LMAH FR CNRS 3335 F-76600 Le Havre France

In this paper, we are interested in the separation problem for the so-called rounded capacity inequalities which are valid for the CVRP (Capacitated Vehicle Routing Problem) polytope. Rounded capacity inequalities, as well as the associated separation problem, are of particular interest for solving the CVRP, especially when dealing with the two-index formulation of the CVRP and Branch-and-Cut algorithms based on this formulation. To the best of our knowledge, it is not known in the literature whether this separation problem is NP-hard or polynomial (see for instance Augerat et al. (1998) and Letchford and Salazar (2015)), and it has been conjectured that the problem is NP-hard. In this paper, we prove this conjecture. We also show that the separation problem for rounded capacity inequalities is strongly NP-hard when the considered solution belongs to a particular relaxation of the problem and the clients have all the same demand. (C) 2017 Elsevier B.V. All rights reserved.

关键词： Branch-and-Cut polyhedral combinatorics Computational complexity Capacitated Vehicle Routing Problem

来源：评论

学校读者我要写书评

暂无评论

An exact solution method for quadratic matching: The one-quadratic-term technique and generalisations

引用

DISCRETE OPTIMIZATION 2015年 18卷 193-216页

作者： Hupp, Lena Klein, Laura Liers, Frauke Univ Erlangen Nurnberg Lehrstuhl Wirtschaftsmath D-91058 Erlangen Germany Tech Univ Dortmund Fak Math D-44227 Dortmund Germany

The quadratic matching problem (QMP) asks for a matching in a graph that optimises a quadratic objective in the edge variables. The QMP generalises the quadratic assignment problem as the latter can be seen as a perfect matching on a bipartite graph. In our approach, we strengthen the linearised IP-formulation by cutting planes that are derived from facets of the corresponding matching problem where only one quadratic term is present in the objective function (QMP1). As the influence of these cutting planes on the root bound decreases for instances with more quadratic terms in the objective, we present different methods to strengthen these cutting planes. Adopting the idea of the reformulation linearisation technique (RLT) we derive valid inequalities for the general QMP from QMP1 facets. Following the approach in Fomeni et al. (2015) we replace cubic terms that appear in a reformulated QMP1 inequality by a quadratic estimator. Based on these methods we design and implement an exact branch-and-cut approach. When compared to solving the standard linearised IP formulation strengthened by cutting planes that result from the application of the RLT to the degree inequalities, we show that root bounds and cpu times for solving instances to optimality can significantly be improved, when the new method is applied. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Binary quadratic optimisation problem Reformulation linearisation technique (RLT) Quadratic matching problem polyhedral combinatorics

来源：评论

学校读者我要写书评

暂无评论

polyhedral approach to weighted connected matchings in general graphs

引用

DISCRETE APPLIED MATHEMATICS 2024年 359卷 143-152页

作者： Samer, Phillippe Moura, Phablo F. S. Univ Bergen Inst Informatikk Postboks 7800 N-5020 Bergen Norway Katholieke Univ Leuven Res Ctr Operat Res & Stat Leuven Belgium

A connected matching in a graph G consists of a set of pairwise disjoint edges whose covered vertices induce a connected subgraph of G . While finding a connected matching of maximum cardinality is a well-solved problem, it is NP-hard to determine an optimal connected matching in an edge-weighted graph, even in the planar bipartite case. We present two mixed integer programming formulations and a sophisticated branch-and- cut scheme to find weighted connected matchings in general graphs. The formulations explore different polyhedra associated to this problem, including strong valid inequalities both from the matching polytope and from the connected subgraph polytope. We conjecture that one attains a tight approximation of the convex hull of connected matchings using our strongest formulation, and report encouraging computational results over DIMACS Implementation Challenge benchmark instances. The source code of the complete implementation is also made available. (c) 2024 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY license (http://***/licenses/by/4.0/).

关键词： Connected matchings Combinatorial optimization polyhedral combinatorics Integer programming Induced connectivity Connected subgraphs

来源：评论

学校读者我要写书评

暂无评论

Dynamic allocation indices for restless projects and queueing admission control:: a polyhedral approach

引用

MATHEMATICAL PROGRAMMING 2002年第3期93卷 361-413页

作者： Niño-Mora, J Univ Pompeu Fabra Dept Econ & Business Barcelona 08005 Spain

This paper develops a polyhedral approach to the design, analysis, and computation of dynamic allocation indices for scheduling binary-action (engage/rest) Markovian stochastic projects which can change state when rested (restless bandits (RBs)), based on partial conservation laws (PCLs). This extends previous work by the author [J. Nino-Mora (2001): Restless bandits, partial conservation laws and indexability. Adv. Appl. Probab. 33, 76-98], where PCLs were shown to imply the optimality of index policies with a postulated structure in stochastic scheduling problems, under admissible linear objectives, and they were deployed to obtain simple sufficient conditions for the existence of Whittle's (1988) RB index (indexability), along with an adaptive-greedy index algorithm. The new contributions include: (i) we develop the polyhedral foundation of the PCL framework, based on the structural and algorithmic properties of a new polytope associated with an accessible set system (J, F) (T-extended polymatroid);(ii) we present new dynamic allocation indices for RBs, motivated by an admission control model, which extend Whittle's and have a significantly increased scope;(iii) we deploy PCLs to obtain both sufficient conditions for the existence of the new indices (PCL-indexability), and a new adaptive-greedy index algorithm;(iv) we interpret PCL-indexability as a form of the classic economics law of diminishing marginal returns, and characterize the index as an optimal marginal cost rate;we further solve a related optimal constrained control problem;(v) we carry out a PCL-indexability analysis of the motivating admission control model, under time-discounted and long-run average criteria;this gives, under mild conditions, a new index characterization of optimal threshold policies;and (vi) we apply the latter to present new heuristic index policies for two hard queueing control problems: admission control and routing to parallel queues;and scheduling a multiclass make-to-stock q

关键词： Markov decision process restless bandits polyhedral combinatorics extended polymatroid adaptive-greedy algorithm dynamic allocation index stochastic scheduling threshold policy index policy Gittins index Klimov index Whittle index control of queues admission control routing make-to-stock multiclass queue finite buffers conservation laws achievable performance

来源：评论

学校读者我要写书评

暂无评论

Optimum partitioning into intersections of ring families

引用

DISCRETE APPLIED MATHEMATICS 1997年第1-3期76卷 81-91页

作者： Cochand, M Gaillard, A Groflin, H UNIV FRIBOURG INST INFORMATIIUFCH-1700 FRIBOURGSWITZERLAND

Given two ring families C and D on a finite ground set V, with both empty set and V is an element of C and D, consider the family of so-called intersections L = {L subset of or equal to V\L = C boolean AND D, C is an element of C, D is an element of D and C boolean OR D = V} and let A be the incidence matrix of L. The minimum partitioning problem: ''Given a vector d is an element of Z(+)(V), minimize y1 s.t. yA = d, y greater than or equal to 0, y integer'', is solved by a longest path computation. The approach is polyhedral and capitalizes on previous results related to lattice matrices.

关键词： polyhedral combinatorics submodular flows lattice matrices

来源：评论

学校读者我要写书评

暂无评论

Cycle-based facets of chromatic scheduling polytopes

引用

DISCRETE OPTIMIZATION 2009年第1期6卷 51-63页

作者： Marenco, Javier Wagler, Annegret Univ Buenos Aires Dept Comp Sci FCEN RA-1428 Buenos Aires DF Argentina Natl Univ Gen Sarmiento Inst Sci RA-1613 Buenos Aires DF Argentina Otto VonGuericke Univ Magdegurg Inst Math Optimizat Fac Math D-39106 Magdeburg Germany

Chromatic scheduling polytopes arise as solution sets of the bandwidth allocation problem in certain radio access networks, which supply wireless access to voice/data communication for customers with fixed antennas and individual demands. This problem is N P-complete and, moreover, does not admit polynomial-time approximation algorithms with a fixed quality guarantee. As algorithms based on cutting planes have shown to be successful for many other combinatorial optimization problems, our goal is to apply such methods to the bandwidth allocation problem. To gain the required knowledge on the associated polytopes, the present paper contributes by considering three new classes of valid inequalities based on cycles in the interference graph. We discuss in which cases they define facets and explore the associated separation problems, showing that two of them are solvable in polynomial time. (C) 2008 Elsevier B.V. All rights reserved.

关键词： Bandwidth allocation polyhedral combinatorics Facets Separation

来源：评论

学校读者我要写书评

暂无评论

Stochastic lot-sizing problem with deterministic demands and Wagner-Whitin Costs

引用

OPERATIONS RESEARCH LETTERS 2010年第5期38卷 414-419页

作者： Zhou, Zhili Guan, Yongpei Univ Florida Dept Ind & Syst Engn Gainesville FL 32611 USA

In this paper, we consider a two-stage stochastic uncapacitated lot-sizing problem with deterministic demands and Wagner-Whitin costs. We develop an extended formulation in the higher dimensional space that provides integral solutions by showing that its constraint matrix is totally unimodular. We also provide the integral polyhedron of the problem in the original space by projecting the extended formulation to the original space. (C) 2010 Elsevier B.V. All rights reserved.

关键词： Stochastic programming Lot-sizing polyhedral combinatorics Integer programming

来源：评论

学校读者我要写书评

暂无评论

THE BOOLEAN QUADRIC POLYTOPE - SOME CHARACTERISTICS, FACETS AND RELATIVES

引用

MATHEMATICAL PROGRAMMING 1989年第1期45卷 139-172页

作者： PADBERG, M 1.Stern School of Business New York University Washington Square 10003 New York NY USA

We study unconstrained quadratic zero–one programming problems havingn variables from a polyhedral point of view by considering the Boolean quadric polytope QP n inn(n+1)/2 dimensions that results from the lineariza... 详细信息

We study unconstrained quadratic zero–one programming problems havingn variables from a polyhedral point of view by considering the Boolean quadric polytope QPⁿ inn(n+1)/2 dimensions that results from the linearization of the quadratic form. We show that QPⁿ has a diameter of one, descriptively identify three families of facets of QPⁿ and show that QPⁿ is symmetric in the sense that all facets of QPⁿ can be obtained from those that contain the origin by way of a mapping. The naive linear programming relaxation QPⁿ _LP of QPⁿ is shown to possess the Trubin-property and its extreme points are shown to be {0,1/2,1}-valued. Furthermore, O(n ³) facet-defining inequalities of QPⁿ suffice to cut off all fractional vertices of QPⁿ _LP, whereas the family of facets described by us has at least O(3ⁿ) members. The problem is also studied for sparse quadratic forms (i.e. when several or many coefficients are zero) and conditions are given for the previous results to carry over to this case. Polynomially solvable problem instances are discussed and it is shown that the known polynomiality result for the maximization of nonnegative quadratic forms can be obtained by simply rounding the solution to the linear programming relaxation. In the case that the graph induced by the nonzero coefficients of the quadratic form is series-parallel, a complete linear description of the associated Boolean quadric polytope is given. The relationship of the Boolean quadric polytope associated to sparse quadratic forms with the vertex-packing polytope is discussed as well.

关键词： Unconstrained zero–one quadratic programming polyhedral combinatorics facets polytopes vertex-packing series-parallel graphs polynomial solvability

来源：评论

学校读者我要写书评

暂无评论

Vertex adjacencies in the set covering polyhedron

引用

DISCRETE APPLIED MATHEMATICS 2017年 218卷 40-56页

作者： Aguilera, Nestor E. Katz, Ricardo D. Tolomei, Paola B. Fac Ingn Quim UNL Santiago del Estero 2829 RA-3000 Santa Fe Argentina CONICET CIFASIS Bv 27 Febrero 210 Bis RA-2000 Rosario Santa Fe Argentina Consejo Nacl Invest Cient & Tecn RA-1033 Buenos Aires DF Argentina Fac Ciencias Exactas Ingn & Agrimensura UNR Pellegrini 250 RA-2000 Rosario Santa Fe Argentina

We describe the adjacency of vertices of the (unbounded version of the) set covering polyhedron, in a similar way to the description given by Chvatal for the stable set polytope. We find a sufficient condition for adjacency, and characterize it with similar conditions in the case where the underlying matrix is row circular. We apply our findings to show a new infinite family of minimally nonideal matrices. (C) 2016 Elsevier B.V. All rights reserved.

关键词： polyhedral combinatorics Set covering polyhedron Vertex adjacency

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：