共查询到20条相似文献,搜索用时 15 毫秒
1.
The Node Weighted Steiner Tree Problem (NW-STP) is a generalization of the Steiner Tree Problem. A lagrangean heuristic presented in EngevallS: StrLBN: 98, and based on
the work in Lucena: 92, solves the problem by relaxing an exponential family of generalized subtour elimination constraints
and taking into account only the violated ones as the computation proceeds. In EngevallS: StrLBN: 98 the computational results
refer to complete graphs up to one hundred vertices. In this paper, we present a branch-and-bound algorithm based on this
formulation. Its performance on the instances from the literature confirms the effectiveness of the approach. The experimentation
on a newly generated set of benchmark problems, more similar to the real-world applications, shows that the approach is still
valid, provided that suitable refinements on the bounding procedures and a preprocessing phase are introduced. The algorithm
solves to optimality all of the considered instances up to one thousand vertices, with the exception of 11 hard instances,
derived from the literature of a similar problem, the Prize Collecting Steiner Tree Problem.
Received: March 2005, Revised: September 2005
AMS classification:
68M10, 90C10, 90C57
This work has been partially supported by the Ministero dell'Istruzione, Universitá e Ricerca (MIUR), Italy 相似文献
2.
Muhong Zhang 《Operations Research Letters》2011,39(5):342-345
In this paper, we consider the two-stage minimax robust uncapacitated lot-sizing problem with interval uncertain demands. A mixed integer programming formulation is proposed. Even though the robust uncapacitated lot-sizing problem with discrete scenarios is an NP-hard problem, we show that it is polynomial solvable under the interval uncertain demand set. 相似文献
3.
Eduardo Uchoa 《Operations Research Letters》2006,34(4):437-444
This article introduces a proper redefinition of the concept of bottleneck Steiner distance for the prize-collecting Steiner problem. This allows the application of reduction tests known to be effective on Steiner problem in graphs in their full power. Computational experiments attest the effectiveness of the proposed tests. 相似文献
4.
We develop a duality theory for minimax fractional programming problems in the face of data uncertainty both in the objective and constraints. Following the framework of robust optimization, we establish strong duality between the robust counterpart of an uncertain minimax convex–concave fractional program, termed as robust minimax fractional program, and the optimistic counterpart of its uncertain conventional dual program, called optimistic dual. In the case of a robust minimax linear fractional program with scenario uncertainty in the numerator of the objective function, we show that the optimistic dual is a simple linear program when the constraint uncertainty is expressed as bounded intervals. We also show that the dual can be reformulated as a second-order cone programming problem when the constraint uncertainty is given by ellipsoids. In these cases, the optimistic dual problems are computationally tractable and their solutions can be validated in polynomial time. We further show that, for robust minimax linear fractional programs with interval uncertainty, the conventional dual of its robust counterpart and the optimistic dual are equivalent. 相似文献
5.
Alysson M. Costa Jean-François Cordeau Gilbert Laporte 《European Journal of Operational Research》2008
This article describes and compares three heuristics for a variant of the Steiner tree problem with revenues, which includes budget and hop constraints. First, a greedy method which obtains good approximations in short computational times is proposed. This initial solution is then improved by means of a destroy-and-repair method or a tabu search algorithm. Computational results compare the three methods in terms of accuracy and speed. 相似文献
6.
Ivana Ljubić René Weiskircher Ulrich Pferschy Gunnar W. Klau Petra Mutzel Matteo Fischetti 《Mathematical Programming》2006,105(2-3):427-449
The Prize-Collecting Steiner Tree Problem (PCST) on a graph with edge costs and vertex profits asks for a subtree minimizing
the sum of the total cost of all edges in the subtree plus the total profit of all vertices not contained in the subtree.
PCST appears frequently in the design of utility networks where profit generating customers and the network connecting them
have to be chosen in the most profitable way.
Our main contribution is the formulation and implementation of a branch-and-cut algorithm based on a directed graph model
where we combine several state-of-the-art methods previously used for the Steiner tree problem. Our method outperforms the
previously published results on the standard benchmark set of problems.
We can solve all benchmark instances from the literature to optimality, including some of them for which the optimum was not
known. Compared to a recent algorithm by Lucena and Resende, our new method is faster by more than two orders of magnitude.
We also introduce a new class of more challenging instances and present computational results for them. Finally, for a set
of large-scale real-world instances arising in the design of fiber optic networks, we also obtain optimal solution values.
Received: April, 2004
This work has been partly supported by the RTNADONET, 504438, by the Doctoral Scholarship Program of the Austrian Academy
of Sciences (DOC) and by CNR and MIUR, Italy.A preliminary version of this paper appeared as [21]. 相似文献
7.
Eduardo lvarez-Miranda Alfredo Candia-Vjar Xu-jin CHEN Xiao-dong HU Bi LI 《应用数学学报(英文版)》2014,30(1):1-26
Given a connected graph G=(V,E)with a nonnegative cost on each edge in E,a nonnegative prize at each vertex in V,and a target set V′V,the Prize Collecting Steiner Tree(PCST)problem is to find a tree T in G interconnecting all vertices of V′such that the total cost on edges in T minus the total prize at vertices in T is minimized.The PCST problem appears frequently in practice of operations research.While the problem is NP-hard in general,it is polynomial-time solvable when graphs G are restricted to series-parallel graphs.In this paper,we study the PCST problem with interval costs and prizes,where edge e could be included in T by paying cost xe∈[c e,c+e]while taking risk(c+e xe)/(c+e c e)of malfunction at e,and vertex v could be asked for giving a prize yv∈[p v,p+v]for its inclusion in T while taking risk(yv p v)/(p+v p v)of refusal by v.We establish two risk models for the PCST problem with interval data.Under given budget upper bound on constructing tree T,one model aims at minimizing the maximum risk over edges and vertices in T and the other aims at minimizing the sum of risks over edges and vertices in T.We propose strongly polynomial-time algorithms solving these problems on series-parallel graphs to optimality.Our study shows that the risk models proposed have advantages over the existing robust optimization model,which often yields NP-hard problems even if the original optimization problems are polynomial-time solvable. 相似文献
8.
Mohamed Haouari Safa Bhar Layeb Hanif D. Sherali 《Computational Optimization and Applications》2008,40(1):13-39
We propose a generalized version of the Prize Collecting Steiner Tree Problem (PCSTP), which offers a fundamental unifying
model for several well-known
-hard tree optimization problems. The PCSTP also arises naturally in a variety of network design applications including cable
television and local access networks. We reformulate the PCSTP as a minimum spanning tree problem with additional packing
and knapsack constraints and we explore various nondifferentiable optimization algorithms for solving its Lagrangian dual.
We report computational results for nine variants of deflected subgradient strategies, the volume algorithm (VA), and the
variable target value method used in conjunction with the VA and with a generalized Polyak–Kelley cutting plane technique.
The performance of these approaches is also compared with an exact stabilized constraint generation procedure. 相似文献
9.
This paper studies the complexity of the robust spanning tree problem with interval data (RSTID). It shows that the problem is NP-complete, settling the conjecture of Kouvelis and Yu, and that it remains so for complete graphs or when the intervals are all [0,1]. These results indicate that the difficulty of RSTID stems from both the graph topology and the structure of the cost intervals, suggesting new directions for search algorithms. 相似文献
10.
Thai Doan Chuong 《Operations Research Letters》2019,47(2):105-109
We first show that the closedness of the characteristic cone of the constraint system of a parametric robust linear optimization problem is a necessary and sufficient condition for each robust linear program with the finite optimal value to admit exact semidefinite linear programming relaxations. We then provide the weakest regularity condition that guarantees exact second-order cone programming relaxations for parametric robust linear programs. 相似文献
11.
The paper concerns a new variant of the hierarchical facility location problem on metric powers (HFLβ[h]), which is a multi-level uncapacitated facility location problem defined as follows. The input consists of a set F of locations that may open a facility, subsets D1,D2,…,Dh−1 of locations that may open an intermediate transmission station and a set Dh of locations of clients. Each client in Dh must be serviced by an open transmission station in Dh−1 and every open transmission station in Dl must be serviced by an open transmission station on the next lower level, Dl−1. An open transmission station on the first level, D1 must be serviced by an open facility. The cost of assigning a station j on level l1 to a station i on level l−1 is cij. For iF, the cost of opening a facility at location i is fi0. It is required to find a feasible assignment that minimizes the total cost. A constant ratio approximation algorithm is established for this problem. This algorithm is then used to develop constant ratio approximation algorithms for the bounded depth Steiner tree problem and the bounded hop strong-connectivity range assignment problem. 相似文献
12.
Robust optimization problems, which have uncertain data, are considered. We prove surrogate duality theorems for robust quasiconvex optimization problems and surrogate min–max duality theorems for robust convex optimization problems. We give necessary and sufficient constraint qualifications for surrogate duality and surrogate min–max duality, and show some examples at which such duality results are used effectively. Moreover, we obtain a surrogate duality theorem and a surrogate min–max duality theorem for semi-definite optimization problems in the face of data uncertainty. 相似文献
13.
For a current deregulated power system, a large amount of operating reserve is often required to maintain the reliability of the power system using traditional approaches. In this paper, we propose a two-stage robust optimization model to address the network constrained unit commitment problem under uncertainty. In our approach, uncertain problem parameters are assumed to be within a given uncertainty set. We study cases with and without transmission capacity and ramp-rate limits (The latter case was described in Zhang and Guan (2009), for which the analysis part is included in Section 3 in this paper). We also analyze solution schemes to solve each problem that include an exact solution approach and an efficient heuristic approach that provides tight lower and upper bounds for the general network constrained robust unit commitment problem. The final computational experiments on an IEEE 118-bus system verify the effectiveness of our approaches, as compared to the nominal model without considering the uncertainty. 相似文献
14.
Selected topics in robust convex optimization 总被引:1,自引:0,他引:1
Robust Optimization is a rapidly developing methodology for handling optimization problems affected by non-stochastic “uncertain-but-
bounded” data perturbations. In this paper, we overview several selected topics in this popular area, specifically, (1) recent
extensions of the basic concept of robust counterpart of an optimization problem with uncertain data, (2) tractability of robust counterparts, (3) links between RO and traditional
chance constrained settings of problems with stochastic data, and (4) a novel generic application of the RO methodology in
Robust Linear Control.
相似文献
15.
In 2004, Bertsimas and Sim proposed a robust approach that can control the degree of conservatism by applying a limitation Γ to the maximum number of parameters that are allowed to change. However, the robust approach can become extremely conservative even when Γ is relatively small. In this paper, we provide a theoretical analysis to explain why this extreme conservatism occurs. We further point out that the robust approach does not reach an extremely conservative state when Γ is less than k, where k is the number of nonzero components of the optimal solution of the extremely conservative robust approach. This research also shows that care must be taken when adjusting the value of Γ to control the degree of conservatism because the approach may result in greater conservatism than was intended. We subsequently apply our analysis to additive combinatorial optimization problems. Finally, we illustrate our results on numerical simulations. 相似文献
16.
This paper presents an approximate affinely adjustable robust counterpart for conic quadratic constraints. The theory is applied
to obtain robust solutions to the problems of subway route design with implementation errors and a supply chain management
with uncertain demands. Comparison of the adjustable solutions with the nominal and non-adjustable robust solutions shows
that the adjustable (dynamic) robust solution maintains feasibility for all possible realizations, while being less conservative
than the usual (static) robust counterpart solution. 相似文献
17.
《Operations Research Letters》2022,50(5):581-587
This paper presents a mixed-integer linear programming formulation for the multi-mode resource-constrained project scheduling problem with uncertain activity durations. We consider a two-stage robust optimisation approach and find solutions that minimise the worst-case project makespan, whilst assuming that activity durations lie in a budgeted uncertainty set. Computational experiments show that this easy-to-implement formulation is many times faster than the current state-of-the-art solution approach for this problem, whilst solving over 40% more instances to optimality over the same benchmarking set. 相似文献
18.
Exact and heuristic methodologies for scheduling in hospitals: problems, formulations and algorithms
Jeroen Beliën 《4OR: A Quarterly Journal of Operations Research》2007,5(2):157-160
This text summarizes the PhD thesis defended by the author in January 2006 under the supervision of Professor Erik Demeulemeester
at the Katholieke Universiteit Leuven. The thesis is written in English and is available from the author’s website (http://www.econ.kuleuven.be/jeroen.belien).
In this research we propose a number of exact and heuristic algorithms for various scheduling problems encountered in hospitals.
The emphasis lies on the design of new methodologies as well as on the applicability of the algorithms in real-life environments.
The main contributions include a new decomposition approach for a particular class of staff scheduling problems, an extensive
study of master surgery scheduling algorithms that aim at leveling the resultant bed occupancy and an innovative method for
integrating nurse and surgery scheduling.
相似文献
19.
Carlos E. Ferreira 《Discrete Applied Mathematics》2006,154(13):1877-1884
The group Steiner tree problem consists of, given a graph G, a collection R 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∈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. 相似文献
20.
Lizhi Wang 《Operations Research Letters》2009,37(2):114-116
We present cutting plane algorithms for the inverse mixed integer linear programming problem (InvMILP), which is to minimally perturb the objective function of a mixed integer linear program in order to make a given feasible solution optimal. 相似文献