The Steiner tree problem II: Properties and classes of facets

This is the second part of two papers addressing the study of the facial structure of the Steiner tree polyhedron. In this paper we identify several classes of facet defining inequalities and relate them to special classes of graphs on which the Steiner tree problem is known to be NP-hard.Corresponding author.The author appreciates partial support from National Science Foundation Grants Nos. DSM-8606188 and ECS 8800281.     

The Steiner tree problem I: Formulations,compositions and extension of facets

In this paper we give some integer programming formulations for the Steiner tree problem on undirected and directed graphs and study the associated polyhedra. We give some families of facets for the undirected case along with some compositions and extensions. We also give a projection that relates the Steiner tree polyhedron on an undirected graph to the polyhedron for the corresponding directed graph. This is used to show that the LP-relaxation of the directed formulation is superior to the LP-relaxation of the undirected one.Corresponding author.     

The Euclidean Steiner tree problem in Rn: A mathematical programming formulation

A nonconvex mixed-integer programming formulation for the Euclidean Steiner Tree Problem (ESTP) in Rⁿ is presented. After obtaining separability between integer and continuous variables in the objective function, a Lagrange dual program is proposed. To solve this dual problem (and obtaining a lower bound for ESTP) we use subgradient techniques. In order to evaluate a subgradient at each iteration we have to solve three optimization problems, two in polynomial time, and one is a special convex nondifferentiable programming problem. This revised version was published online in June 2006 with corrections to the Cover Date.     

系列平行图上带时间约束的Steiner最小树问题

对一类特殊系列平行图上带有时间约束的Steiner最小树问题,证明了其复杂性为NPC,并给出了一个完全多项式时间近似方案.     

Exact approaches for solving robust prize-collecting Steiner tree problems

In the Prize-Collecting Steiner Tree Problem (PCStT) we are given a set of customers with potential revenues and a set of possible links connecting these customers with fixed installation costs. The goal is to decide which customers to connect into a tree structure so that the sum of the link costs plus the revenues of the customers that are left out is minimized. The problem, as well as some of its variants, is used to model a wide range of applications in telecommunications, gas distribution networks, protein–protein interaction networks, or image segmentation.     

The Steiner tree polytope and related polyhedra

We consider the vertex-weighted version of the undirected Steiner tree problem. In this problem, a cost is incurred both for the vertices and the edges present in the Steiner tree. We completely describe the associated polytope by linear inequalities when the underlying graph is series—parallel. For general graphs, this formulation can be interpreted as a (partial) extended formulation for the Steiner tree problem. By projecting this formulation, we obtain some very large classes of facet-defining valid inequalities for the Steiner tree polytope.Research supported by Air Force contract AFOSR-89-0271 and DARPA contract DARPA-89-5-1988.     

Fast heuristics for the Steiner tree problem with revenues,budget and hop constraints

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.     

The steiner tree packing problem in VLSI design

In this paper we describe several versions of the routing problem arising in VLSI design and indicate how the Steiner tree packing problem can be used to model these problems mathematically. We focus on switchbox routing problems and provide integer programming formulations for routing in the knock-knee and in the Manhattan model. We give a brief sketch of cutting plane algorithms that we developed and implemented for these two models. We report on computational experiments using standard test instances. Our codes are able to determine optimum solutions in most cases, and in particular, we can show that some of the instances have no feasible solution if Manhattan routing is used instead of knock-knee routing.     

求解最小Steiner树的蚁群优化算法及其收敛性

最小Steiner树问题是NP难问题,它在通信网络等许多实际问题中有着广泛的应用．蚁群优化算法是最近提出的求解复杂组合优化问题的启发式算法．本文以无线传感器网络中的核心问题之一,路由问题为例,给出了求解最小Steiner树的蚁群优化算法的框架．把算法的迭代过程看作是离散时间的马尔科夫过程,证明了在一定的条件下,该算法所产生的解能以任意接近于1的概率收敛到路由问题的最优解．     

The robust minimum spanning tree problem: Compact and convex uncertainty

We consider the robust minimum spanning tree problem where edges costs are on a compact and convex subset of Rⁿ. We give the location of the robust deviation scenarios for a tree and characterizations of strictly strong edges and non-weak edges leading to recognition algorithms.     

Optimal scheduling of reservoir releases during flood: Deterministic optimization problem,part 2, case study

This paper applies the optimization procedure developed in Part 1 to the problem of the optimal scheduling of reservoir releases during flood in the case study concerning the river system of Upper Vistula in Poland. Technical details related to the implementation of the proposed algorithm are discussed.The research reported here has been supported by the Central Basic Research Program CPBP-03.09, Metody Analizy i Uytkowania Aasobow Wodnych, Polish Academy of Sciences, Warsaw, Poland. This support is kindly acknowledged.     

Lagrangian bounds in multiextremal polynomial and discrete optimization problems

Many polynomial and discrete optimization problems can be reduced to multiextremal quadratic type models of nonlinear programming. For solving these problems one may use Lagrangian bounds in combination with branch and bound techniques. The Lagrangian bounds may be improved for some important examples by adding in a model the so-called superfluous quadratic constraints which modify Lagrangian bounds. Problems of finding Lagrangian bounds as a rule can be reduced to minimization of nonsmooth convex functions and may be successively solved by modern methods of nondifferentiable optimization. This approach is illustrated by examples of solving polynomial-type problems and some discrete optimization problems on graphs.     

The minimum-area spanning tree problem

Motivated by optimization problems in sensor coverage, we formulate and study the Minimum-Area Spanning Tree (mast) problem: Given a set of n points in the plane, find a spanning tree of of minimum “area”, where the area of a spanning tree is the area of the union of the n−1 disks whose diameters are the edges in . We prove that the Euclidean minimum spanning tree of is a constant-factor approximation for mast. We then apply this result to obtain constant-factor approximations for the Minimum-Area Range Assignment (mara) problem, for the Minimum-Area Connected Disk Graph (macdg) problem, and for the Minimum-Area Tour (mat) problem. The first problem is a variant of the power assignment problem in radio networks, the second problem is a related natural problem, and the third problem is a variant of the traveling salesman problem.     

The minimum spanning tree problem with fuzzy costs

In this paper the minimum spanning tree problem in a given connected graph is considered. It is assumed that the edge costs are not precisely known and they are specified as fuzzy intervals. Possibility theory is applied to characterize the optimality of edges of the graph and to choose a spanning tree under fuzzy costs.     

Packing Steiner trees: a cutting plane algorithm and computational results

In this paper we describe a cutting plane algorithm for the Steiner tree packing problem. We use our algorithm to solve some switchbox routing problems of VLSI-design and report on our computational experience. This includes a brief discussion of separation algorithms, a new LP-based primal heuristic and implementation details. The paper is based on the polyhedral theory for the Steiner tree packing polyhedron developed in our companion paper (this issue) and meant to turn this theory into an algorithmic tool for the solution of practical problems.     

Optimal scheduling of reservoir releases during flood: Deterministic optimization problem,part 1, procedure

In this paper, we are concerned with the optimal scheduling of water releases from retention reservoirs during flood, with the objective of minimizing flood damages at the important damage centers downstream of the reservoirs. Unlike in most other papers devoted to this subject, the flood routing equations are nonlinear. The performance index of the problem leads to a minimax optimal control problem. For this problem, the necessary optimality conditions are provided and a version of the feasible directions method is proposed.The research reported here has been supported by the Central Basic Research Program CPBP-03.09, Metody Analizy i Uytkowania Zasobow Wodnych, Polish Academy of Sciences, Warsaw, Poland. This support is kindly acknowledged.     

GRASP with hybrid heuristic-subproblem optimization for the multi-level capacitated minimum spanning tree problem

We propose a GRASP using an hybrid heuristic-subproblem optimization approach for the Multi-Level Capacitated Minimum Spanning Tree (MLCMST) problem. The motivation behind such approach is that to evaluate moves rearranging the configuration of a subset of nodes may require to solve a smaller-sized MLCMST instance. We thus use heuristic rules to define, in both the construction and the local search phases, subproblems which are in turn solved exactly by employing an integer programming model. We report numerical results obtained on benchmark instances from the literature, showing the approach to be competitive in terms of solution quality. The proposed GRASP have in fact improved the best known upper bounds for almost all of the considered instances.     

A survey on the global optimization problem: General theory and computational approaches

Several different approaches have been suggested for the numerical solution of the global optimization problem: space covering methods, trajectory methods, random sampling, random search and methods based on a stochastic model of the objective function are considered in this paper and their relative computational effectiveness is discussed. A closer analysis is performed of random sampling methods along with cluster analysis of sampled data and of Bayesian nonparametric stopping rules.