Spanning trees with a constraint on the number of leaves. A new formulation

In this paper we present a new extended model for the problem of finding a minimum cost spanning tree such that the number of leaves is equal to (greater than, less than) k. We show that with these variables we are able to derive stronger linking constraints in a flow based model permitting us, by using projection techniques, to derive a model with enhanced cut constraints. The new variables also permit us to strengthen, in an extended space, strong inequalities that are well known from the literature. We show that the strengthened inequalities imply a set of inequalities of exponential size, as presented previously by Fujie [8]. A new set of inequalities of exponential size are also implied by the new model will also be proposed. We also discuss the new model in the context of a related problem, the max-leaves problem where one wants to find a spanning tree with a maximum number of leaves. Computational results taken from several sets of instances known from the literature indicate that the new model improves previously known gaps for the three constrained versions and that despite the extra number of variables, it leads to best solution times in almost all cases. For the max-leaves problem the new model proves to be competitive with the existent approaches.     

Solving the variable size bin packing problem with discretized formulations

In this paper we study the use of a discretized formulation for solving the variable size bin packing problem (VSBPP). The VSBPP is a generalization of the bin packing problem where bins of different capacities (and different costs) are available for packing a set of items. The objective is to pack all the items minimizing the total cost associated with the bins. We start by presenting a straightforward integer programming formulation to the problem and later on, propose a less straightforward formulation obtained by using a so-called discretized model reformulation technique proposed for other problems (see [Gouveia L. A 2n constraint formulation for the capacitated minimal spanning tree problem. Operations Research 1995; 43:130–141; Gouveia L, Saldanha-da-Gama F. On the capacitated concentrator location problem: a reformulation by discretization. Computers and Operations Research 2006; 33:1242–1258]). New valid inequalities suggested by the variables of the discretized model are also proposed to strengthen the original linear relaxation bounds. Computational results (see Section 4) with up to 1000 items show that these valid inequalities not only enhance the linear programming relaxation bound but may also be extremely helpful when using a commercial package for solving optimally VSBPP.     

基于加权中值滤波的MST立体匹配算法

传统的最小生成树立体匹配算法对低纹理区域和遮挡区域不敏感,虽然最小生成树立体匹配算法后处理的中值滤波能够消除噪点,但是不能够消除边缘模糊。本文提出一种改进算法来克服这些局限性。首先,由于最小生成树匹配成本区分度不够高,研究并提出新最小生成树的匹配成本,使其可以减小不敏感区域的误匹配。其次,在后处理中使用加权中值滤波,以改善深度图像边缘。实验结果表明,在最小生成树立体匹配算法中使用改进匹配成本算法和加权中值滤波算法,在Middlebury数据集中平均误匹配率达到6.9%,本文算法在Middlebury和KITTI场景中都优于最小生成树立体匹配算法。     

Computational comparisons of different formulations for the Stackelberg minimum spanning tree game

Let be a given graph whose edge set is partitioned into a set R of red edges and a set B of blue edges, and assume that red edges are weighted and contain a spanning tree of G. Then, the Stackelberg minimum spanning tree game (StackMST) is that of pricing (i.e., weighting) the blue edges in such a way that the total weight of the blue edges selected in a minimum spanning tree of the resulting graph is maximized. In this paper, we present different new mathematical programming formulations for the StackMST based on the properties of the minimum spanning tree problem and the bilevel optimization. We establish a theoretical and empirical comparison between these new formulations that are able to solve random instances of 20–70 nodes. We also test our models on instances in the literature, outperforming previous results.     

Min-degree constrained minimum spanning tree problem: New formulation via Miller–Tucker–Zemlin constraints

Given an undirected network with positive edge costs and a positive integer $d>2$, the minimum-degree constrained minimum spanning tree problem is the problem of finding a spanning tree with minimum total cost such that each non-leaf node in the tree has a degree of at least $d$. This problem is new to the literature while the related problem with upper bound constraints on degrees is well studied. Mixed-integer programs proposed for either type of problem is composed, in general, of a tree-defining part and a degree-enforcing part. In our formulation of the minimum-degree constrained minimum spanning tree problem, the tree-defining part is based on the Miller–Tucker–Zemlin constraints while the only earlier paper available in the literature on this problem uses single and multi-commodity flow-based formulations that are well studied for the case of upper degree constraints. We propose a new set of constraints for the degree-enforcing part that lead to significantly better solution times than earlier approaches when used in conjunction with Miller–Tucker–Zemlin constraints.     

基于最小生成树的图像分割

基于最小生成树思想,给出了一种利用改进的最小生成树进行图像分割的方案,减少了最小生成树的构建过程,对初分割的结果利用NNG算法进行合并。该方案节约了分割时间,并且对分割后的图像进行了有效的合并,达到了较好的分割效果。     

Layered graph models and exact algorithms for the generalized hop-constrained minimum spanning tree problem

This paper studies the generalized hop-constrained minimum spanning tree problem (GHMSTP) which has applications in backbone network design subject to quality-of-service constraints that restrict the maximum number of intermediate routers along each communication path. Different possibilities to model the GHMSTP as an integer linear program and strengthening valid inequalities are studied. The obtained formulations are compared theoretically, i.e., by means of their linear programming relaxation. In addition, branch-and-cut approaches based on these formulations are developed and compared in a computational study.     

基于“最小差值法”的网络模型耗费代价研究

最小生成树算法是数据结构中,求网络模型耗费代价最优解的一个重要工具。现实生活中的连通网络模型复杂而多变,有时还需兼顾其它的目标,一棵最小生成树不足以解决问题,因此找出所有的最小生成树是很有必要的,在此提出一种新的寻找所有最小生成树的算法--最小差值法。无向连通图网络通过去掉连枝生成最小生成树,一个连枝加入最小生成树形成一个圈。这种算法是在一个圈中,用连枝的权与其它树枝的权分别作差,求最小差值。由最小差值是否为零,判断原有的最小生成树能否通过换进换出边,生成新的最小生成树。该算法能够有规律、高效率的寻找出所有的最小生成树。在找出的所有最小生成树方案中,选择符合实时情况的最小生成树方案,该方案即为网络耗费代价的最优解。     

On the red/blue spanning tree problem

A geometric spanning tree of a point set S is a tree whose vertex set is S and whose edge set is a set of non-crossing straight line segments with endpoints in S. Given a set of red points and a set of blue points in the plane, the red/blue spanning tree problem is to find a geometric spanning tree for red points and a geometric spanning tree for blue points such that the number of crossing points of the two trees is a minimum. If no three points are collinear, we show that the minimum number of crossing points is completely determined by the number of maximal red (or blue) chains on the convex hull of all red points and blue points. We design an optimal algorithm for constructing a geometric spanning tree of all the red points and a geometric spanning tree of all the blue points with the minimum number of crossing points. If collinear points are allowed, we prove that the problem of deciding whether there exists a geometric spanning path of all the red points and a geometric spanning path of all the blue points without crossing is NP-complete.     

Enhanced second order algorithm applied to the capacitated minimum spanning tree problem

Given a centralized undirected graph with costs associated with its edges, the capacitated minimum spanning tree problem is to find a minimum cost spanning tree of the given graph, subject to a capacity constraint in all subtrees incident in the central node. As the problem is NP-hard, we propose an enhanced version of the well-known second order algorithm, described in [Karnaugh M. A new class of algorithms for multipoint network optimization. IEEE Transactions on Communications 1976;COM-24:500–5.]. The original version of this algorithm is based on a look-ahead strategy, used for a tentative inclusion of a constraint to the problem, performed in each iteration. In the new enhanced version, we propose the inclusion of look-behind steps, which can be seen as the reverse of the look-ahead procedure. Therefore and using some memory features, the method can continue even when facing the traditional stopping criterion of the original algorithm. Computational experiments showing the effectiveness of the new method on benchmark instances are reported.     

Network flow models for the local access network expansion problem

In the local access network expansion problem we need to expand a given network (with tree topology) due to traffic demand increase. We can expand the network either by increasing the capacity of its edges and/or by installing equipments that concentrate the traffic of several demand points. This problem has received some attention in the literature. Here, we view the problem as an extension of the well-known capacitated minimum spanning tree problem. We adapt two types of flow-based formulations, aggregated and disaggregated formulations and present some valid inequalities to improve the linear programming bounds of the previous formulations.     

基于改进的遗传算法的多目标优化问题研究

研究多目标优化算法问题,针对传统的多目标优化算法由于计算复杂度非常高,难以获得令人满意的解等问题,在图论和遗传算法基础上,提出了一种改进的遗传算法求解多目标优化方法。首先采用二进制编码表示最小树问题,然后采用深度优先搜索算法进行图的连通性判断,给出了一种新的适应度函数,以提高算法执行速度和进化效率。最后仿真结果表明,与经典的Prim算法和Kruskal算法相比,新算法复杂度较低,并能在第一次遗传进化过程中获得一批最小生成树,适合于解决不同类型的多目标最小树问题。     

模糊权值网络最小生成树问题的矩阵算法

通过研究模糊权值网络中的最小生成树问题,使用基于模糊数的结构元加权序和经典最小生成树问题的改进权矩阵法,本文提出一种求解边权值为三角模糊数的模糊权值网络最小生成树问题的矩阵算法,并对算法的复杂度和正确性进行分析。通过实例验证了该算法的有效性。     

求解多目标最小生成树问题的改进算法

多目标最小生成树问题是典型的NP问题,Zhou和Gen提出了一种用于计数多目标最小生成树问题的所有非劣最优最小生成树的算法,但该算法无法保证能够找到所有非劣最优最小生成树.针对此问题,提出一种改进的计数算法,并定性说明改进算法能够找到问题的所有非劣最优最小生成树.改进算法在进行子树剔除时增加了一些条件.模拟实验结果表明,改进后的计数算法能够找到所有的非劣最优解.这也说明该算法具有应用的潜力.     

The cost optimal solution of the multi-constrained multicast routing problem

In this paper, we define the cost optimal solution of the multi-constrained multicast routing problem. This problem consists in finding a multicast structure that spans a source node and a set of destinations with respect to a set of constraints, while minimizing a cost function. This optimization is particularly interesting for multicast network communications that require Quality of Service (QoS) guarantees. Finding such a structure that satisfies the set of constraints is an NP-hard problem. To solve the addressed routing problem, most of the proposed algorithms focus on multicast trees. In some cases, the optimal spanning structure (i.e. the optimal multicast route) is neither a tree nor a set of trees nor a set of optimal QoS paths. The main result of our study is the exact identification of this optimal solution. We demonstrate that the optimal connected partial spanning structure that solves the multi-constrained multicast routing problem always corresponds to a hierarchy, a recently proposed generalization of the tree concept. We define the directed partial minimum spanning hierarchies as optimal solutions for the multi-constrained multicast routing problem and analyze their relevant properties. To our knowledge, our paper is the first study that exactly describes the cost optimal solution of this NP-hard problem.     

求解度约束最小生成树问题的新算法

针对网络设计和组合优化中的度约束最小生成树问题,基于第k最小生成树的求解算法,提出了一种求解网络G关于指定节点的最小k度生成树的新算法。该算法通过对网络G的最小生成树作最优可行变换,逐步构造出指定节点的度数越来越接近度约束k的最小i度生成树,最终得到了网络G关于指定节点的最小k度生成树。给出了算法实施的具体步骤,并证明了算法的正确性。最后通过仿真结果和一个运输实例,表明了该算法在解决度约束最小生成树问题中的有效性。     

求解度约束最小生成树的一种改进算法

度约束最小生成树问题是网络设计和优化中的一个NP-hard问题。提出一种求解网络G关于指定节点的最大度约束最小生成树的改进算法。算法在保证指定节点最大度的前提下,通过选取剩余边中权最小的边加入当前网络,得到网络G关于指定节点的最大度最小生成树,同时对算法的复杂度进行了分析。最后通过与其他算法的仿真比较,表明新算法的有效性和通用性。     

Efficient minimum spanning tree construction without Delaunay triangulation

Given n points in a plane, a minimum spanning tree is a set of edges which connects all the points and has a minimum total length. A naive approach enumerates edges on all pairs of points and takes at least Ω(n2) time. More efficient approaches find a minimum spanning tree only among edges in the Delaunay triangulation of the points. However, Delaunay triangulation is not well defined in rectilinear distance. In this paper, we first establish a framework for minimum spanning tree construction which is based on a general concept of spanning graphs. A spanning graph is a natural definition and not necessarily a Delaunay triangulation. Based on this framework, we then design an O(nlogn) sweep-line algorithm to construct a rectilinear minimum spanning tree without using Delaunay triangulation.     

A Functional Approach to External Graph Algorithms

We present a new approach for designing external graph algorithms and use it to design simple, deterministic and randomized external algorithms for computing connected components, minimum spanning forests, bottleneck minimum spanning forests, maximal independent sets (randomized only), and maximal matchings in undirected graphs. Our I/ O bounds compete with those of previous approaches. We also introduce a semi-external model, in which the vertex set but not the edge set of a graph fits in main memory. In this model we give an improved connected components algorithm, using new results for external grouping and sorting with duplicates. Unlike previous approaches, ours is purely functional—without side effects—and is thus amenable to standard checkpointing and programming language optimization techniques. This is an important practical consideration for applications that may take hours to run.     

Improved Binary Space Partition merging

This paper presents a new method for evaluating boolean set operations between Binary Space Partition (BSP) trees. Our algorithm has many desirable features, including both numerical robustness and O(n) output sensitive time complexity, while simultaneously admitting a straightforward implementation. To achieve these properties, we present two key algorithmic improvements. The first is a method for eliminating null regions within a BSP tree using linear programming. This replaces previous techniques based on polygon cutting and tree splitting. The second is an improved method for compressing BSP trees based on a similar approach within binary decision diagrams. The performance of the new method is analyzed both theoretically and experimentally. Given the importance of boolean set operations, our algorithms can be directly applied to many problems in graphics, CAD and computational geometry.