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...
详细信息
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.
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 nontermi...
详细信息
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-pricealgorithms. 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,
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 ...
详细信息
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.
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 incorpor...
详细信息
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.
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, ...
详细信息
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.
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 wit...
详细信息
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
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, eac...
详细信息
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.
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...
详细信息
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.
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 ...
详细信息
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.
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 batchsiz...
详细信息
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.
暂无评论