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

An exact algorithm for the Partition Coloring Problem

COMPUTERS & OPERATIONS RESEARCH 2018年 92卷 170-181页

作者： Furini, Fabio Malaguti, Enrico Santini, Alberto PSL Res Univ Univ Paris Dauphine CNRS F-75016 Paris France Univ Bologna DEI I-40136 Bologna Italy Univ Pompeu Fabra Dept Econ & Empresa Barcelona Spain Barcelona GSE Barcelona Spain

We study the Partition Coloring Problem (PCP), a generalization of the Vertex Coloring Problem where the vertex set is partitioned. The PCP asks to select one vertex for each subset of the partition in such a way that the chromatic number of the induced graph is minimum. We propose a new Integer Linear Programming formulation with an exponential number of variables. To solve this formulation to optimality, we design an effective branch-and-price algorithm. Good quality initial solutions are computed via a new metaheuristic algorithm based on adaptive large neighborhood search. Extensive computational experiments on a benchmark test of instances from the literature show that our branch-and-price algorithm, combined with the new metaheuristic algorithm, is able to solve for the first time to proven optimality several open instances, and compares favorably with the current state-of-the-art exact algorithm. (C) 2018 Elsevier Ltd. All rights reserved.

关键词： Vertex Coloring Partitioning coloring Selective coloring Column generation branch-and-price algorithm

来源：评论

学校读者我要写书评

暂无评论

The multi-terminal vertex separator problem: Complexity, Polyhedra and algorithms

The multi-terminal vertex separator problem: Complexity, Pol...

引用

作者： Youcef Magnouche PSL Research University

学位级别：博士

This thesis deals with the multi-terminal vertex separator problem. Given a graph G = (V ∪T, E) with V ∪T the set of vertices, where T is a set of terminals, and a weight function w: V → Z, associated with nonterminal nodes, the multi-terminal vertex separator problem consists in partitioning V ∪ T into k + 1 subsets {S, V 1,..., V k } such that there is no edge between two different subsets V i and V j, each V i contains exactly one terminal and the weight of S is minimum. In this thesis, we consider the problem from a polyhedral point of view. We give two integer programming formulations for the problem, for one of them, we investigate the related polyhedron and discuss its polyhedral structure. We describe some valid inequalities and characterize when these inequalities define facets. We also derive separation algorithms for these inequalities. Using these results, we develop a branch-and-Cut algorithm for the problem, along with an extensive computational study is presented. We also study the multi-terminal vertex separator polytope in the graphs decompos- able by one node cutsets. If G is a graph that decomposes into G 1 and G 2, we show that the multi-terminal vertex separator polytope in G can be described from two lin- ear systems related to G 1 and G 2. This gives rise to a technique for characterizing the multi-terminal vertex separator polytope in the graphs that are recursively decompos- able. We also obtain a procedure to describe facets for this polytope and show that the multi-terminal vertex separator problem can also be decomposed. Applications of this technique are also discussed. Moreover, we propose three extended formulations for the problem and derive branch- and-price and branch-and-Cut-and-price algorithms. For each formulation we present a column generation scheme to solve the linear relaxation, the way to compute the dual bound and the branching scheme. We present computational results and discuss the performance of each algorithm. Further,

关键词： Combinatorial optimization Polytope Facet branch-and-Cut algorithm branch-and-price algorithm Composition of polyhedra

来源：评论

学校读者我要写书评

暂无评论

An integer programming approach to the bloodmobile routing problem

引用

TRANSPORTATION RESEARCH PART E-LOGISTICS AND TRANSPORTATION REVIEW 2016年第Feb.期86卷 94-115页

作者： Gunpinar, Serkan Centeno, Grisselle Univ S Florida Dept Ind & Management Syst Engn 4202 E Fowler Ave Tampa FL 33620 USA

Every day, a blood center must determine a set of locations among a group of potential sites to route their vehicles for blood collection so as to avoid shortfalls. In this study, a vehicle routing problem is modeled using an integer programming approach to simultaneously identify number of bloodmobiles to operate and minimize the distance travelled. Additionally, the model is extended to incorporate uncertainty in blood potentials and variable durations in bloodmobile visits. Optimal routings are determined using CPLEX solver and branch-and-price algorithm. Results show that proposed algorithm solve the problem to optimality up to 30 locations within 3600 s. (C) 2015 Elsevier Ltd. All rights reserved.

关键词： Vehicle routing problem Health care application Mobile blood collection branch-and-price algorithm Robust optimization Operations research

来源：评论

学校读者我要写书评

暂无评论

On the Design of Complex Networks through a branch-and-price algorithm

On the Design of Complex Networks through a Branch-and-Price...

引用

Globecom Workshops

作者： Souza, Fernanda S. H. Cunha, Alexandre S. Mateus, Geraldo R. Univ Fed Minas Gerais Dept Comp Sci Belo Horizonte MG Brazil

ISBN: (纸本)9781424488650

In this paper, we present a branch-and-price algorithm for solving the Optimal Topology Design Problem of complex networks, based on a tightened deterministic formulation for the problem. The algorithm, which incorporates a delayed column generation approach within a branch-and-bound framework, was proven to work well, being capable of finding optimal topologies within very low computational times, for networks with up to 6 0 nodes and different budget ranges. The algorithm allowed us to conclude that, by modifying the budget size values in our optimization model, different network features are found in optimal solutions. Accordingly, the budget size plays a similar role played by the probability of addition or rewiring arcs in randomized procedures for generating network topologies.

关键词： branch-and-price algorithm complex network design delayed column generation approach optimal topology design problem optimisation optimization model probability probability telecommunication network topology tightened deterministic formulation

来源：评论

学校读者我要写书评

暂无评论

Directed weighted improper coloring for cellular channel allocation

引用

DISCRETE APPLIED MATHEMATICS 2015年 182卷 46-60页

作者： Archetti, Claudia Bianchessi, Nicola Hertz, Alain Colombet, Adrien Gagnon, Francois Univ Brescia Dept Quantitat Methods Brescia Italy Univ Brescia Dept Informat Engn Brescia Italy Ecole Polytech Dept Math & Ind Engn Montreal PQ H3C 3A7 Canada Ecole Hautes Etud Commerciales Gerad Montreal PQ Canada Ecole Technol Super Dept Elect Engn Montreal PQ Canada

Given a directed graph with weights on the vertices and on the arcs, a theta-improper k-coloring is an assignment of at most k different colors to the vertices of G such that the weight of every vertex nu is greater, by a given factor 1/theta, than the sum of the weights on the arcs (u, nu) entering nu with the tail u of the same color as nu. For a given real number theta, we consider the problem of determining the minimum integer k such that G has a theta-improper k-coloring. Also, for a given integer k, we consider the problem of determining the minimum real number 0 such that G has a theta-improper k-coloring. We show that these two problems can be used to model channel allocation problems in wireless communication networks, when it is required that the power of the signal received at a base station is greater, by a given factor, than the sum of interfering powers received from mobiles which are assigned the same channel. We propose set partitioning formulations for both problems and describe branch-and-price algorithms to solve them. Computational experiments are reported for instances having a similar structure as real channel allocation problems. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Graph coloring Weighted directed graphs Channel assignment Set partitioning formulations branch-and-price algorithm

来源：评论

学校读者我要写书评

暂无评论

Incomplete Service and Split Deliveries in a Routing Problem with Profits

引用

NETWORKS 2014年第2期63卷 135-145页

作者： Archetti, Claudia Bianchessi, Nicola Speranza, M. Grazia Hertz, Alain Univ Brescia Dept Quantitat Methods Brescia Italy Ecole Polytech Dept Math & Ind Engn Montreal PQ H3C 3A7 Canada HEC Gerad Montreal PQ Canada

In this article, we study a variant of the capacitated team orienteering problem, that is the problem where a fleet of vehicles, each with a constraint on the time available, is given to serve profitable customers with the objective of maximizing the collected profit. We study the variant where customers may be only partially served (incomplete service) and, if beneficial, also by more than one vehicle (split deliveries). We will analyze the maximum theoretical increase of the profit due to the incomplete service and to the split deliveries. We also computationally measure such increase on a set of instances, by means of an exact algorithm on small/medium size instances and of two heuristics on instances of larger size. (c) 2013 Wiley Periodicals, Inc. NETWORKS, Vol. 63(2), 135-145 2014

关键词： routing problems with profits worst-case analysis branch-and-price algorithm tabu search split delivery

来源：评论

学校读者我要写书评

暂无评论

A branch-and-price algorithm for placement routing for a multi-head beam-type component placement tool

引用

OR SPECTRUM 2008年第3期30卷 515-534页

作者： Sun, Dong-Seok Lee, Tae-Eog Korea Adv Inst Sci & Technol Dept Ind Engn Taejon 305701 South Korea Samsung Elect Syst Engn Team Taean Eup Hwasung City Geonggi Do South Korea

We develop a branch-and-price procedure for a placement routing problem for a multi-head beam-type component placement tool. The problem is modelled as an integer programming model with a huge number of variables, each of which corresponds to a placement route. Its linear programming relaxation is solved by a column generation method. For the column generation subproblem to determine the columns to be added, we develop a dynamic programming procedure. We also propose an effective branching rule to partition the current solution space to eliminate the current fractional solution. Through experiments using real tool data, we observe that the LP relaxation solution value is noticeably close to an integer optimal solution value and hence the integer program formulation and the column generation approach are effective.

关键词： component placement tool placement routing column generation branch-and-price algorithm

来源：评论

学校读者我要写书评

暂无评论

A branch-and-price approach for the partition coloring problem

引用

OPERATIONS RESEARCH LETTERS 2011年第2期39卷 132-137页

作者： Hoshino, Edna A. Frota, Yuri A. de Souza, Cid C. Univ Estadual Campinas Inst Comp BR-13083852 Campinas SP Brazil Univ Fed Mato Grosso do Sul Fac Comp Campo Grande Brazil Univ Fed Fluminense Dept Comp Sci Niteroi RJ Brazil

This work proposes a new integer programming model for the partition coloring problem and a branch-and-price algorithm to solve it. Experiments are reported for random graphs and instances originating from routing and wavelength assignment problems arising in telecommunication network design. We show that our method largely outperforms previously existing approaches. (c) 2011 Elsevier B.V. All rights reserved.

关键词： Graph coloring Integer programming Column generation branch-and-price algorithm

来源：评论

学校读者我要写书评

暂无评论

Optimization models for targeted offers in direct marketing: Exact and heuristic algorithms

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2011年第3期210卷 670-683页

作者： Nobibon, Fabrice Talla Leus, Roe Spieksma, Frits C. R. Katholieke Univ Leuven Operat Res Grp B-3000 Louvain Belgium

This paper presents an optimization model for the selection of sets of clients that will receive an offer for one or more products during a promotion campaign. We show that the problem is strongly NP-hard and that it is unlikely that a constant-factor approximation algorithm can be proposed for solving this problem. We propose an alternative set-covering formulation and develop a branch-and-price algorithm to solve it. We also describe eight heuristics to approximate an optimal solution, including a depth-first branch-and-price heuristic and a tabu-search algorithm. We perform extensive computational experiments both with the exact as well as with the heuristic algorithms. Based on our experiments, we suggest the use of optimal algorithms for small and medium-size instances, while heuristics (especially tabu search and branch-and-price-based routines) are preferable for large instances and when time is an important factor. (C) 2010 Elsevier B.V. All rights reserved.

关键词： Direct marketing campaign Integer programming branch-and-price algorithm Non-approximability Heuristics Tabu search

来源：评论

学校读者我要写书评

暂无评论

A branch-and-price algorithm for multistage stochastic integer programming with application to stochastic batch-sizing problems

引用

MANAGEMENT SCIENCE 2004年第6期50卷 786-796页

作者： Lulli, G Sen, S Univ Arizona Dept Syst & Ind Engn Tucson AZ 85721 USA

In this paper, we present. a branch-and-price method to solve special structured multistage stochastic integer programming problems: We validate our method on two different versions of a multistage stochastic batchsizing problem (SBSP). One version adopts a recourse formulation, and the other is based on probabilistic constraints. Our algorithmic approach is applicable to both formulations. Our computational results suggest that both classes of problems can be solved using relatively few nodes of a branch-and-price tree. The success of our approach calls for extensions in methodology as well as applications.

关键词： stochastic programming integer programming batch sizing branch-and-price algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：