Lower bounds for the Quadratic Minimum Spanning Tree Problem based on reduced cost computation

The Minimum Spanning Tree Problem (MSTP) is one of the most known combinatorial optimization problems. It concerns the determination of a minimum edge-cost subgraph spanning all the vertices of a given connected graph. The Quadratic Minimum Spanning Tree Problem (QMSTP) is a variant of the MSTP whose cost considers also the interaction between every pair of edges of the tree. In this paper we review different strategies found in the literature to compute a lower bound for the QMSTP and develop new bounds based on a reformulation scheme and some new mixed 0–1 linear formulations that result from a reformulation–linearization technique (RLT). The new bounds take advantage of an efficient way to retrieve dual information from the MSTP reduced cost computation. We compare the new bounds with the other bounding procedures in terms of both overall strength and computational effort. Computational experiments indicate that the dual-ascent procedure applied to the new RLT formulation provides the best bounds at the price of increased computational effort, while the bound obtained using the reformulation scheme seems to reasonably tradeoff between the bound tightness and computational effort.     

The quadratic minimum spanning tree problem: A lower bounding procedure and an efficient search algorithm

In this paper we consider the quadratic minimum spanning tree problem (QMSTP) which is known to be NP-hard. Given a complete graph, the QMSTP consists of finding a minimum spanning tree (MST) where interaction costs between pairs of edges are prescribed. A Lagrangian relaxation procedure is devised and an efficient local search algorithm with tabu thresholding is developed. Computational experiments are reported on standard test instances, randomly generated test instances and quadratic assignment problem (QAP) instances from the QAPLIB by using a transformation scheme. The local search heuristic yields very good performance and the Lagrangian relaxation procedure gives the tightest lower bounds for all instances when compared to previous lower bounding approaches.     

The multi-weighted Steiner tree problem: A reformulation by intersection

We propose a new formulation for the multi-weighted Steiner tree (MWST) problem. This formulation is based on the fact that a previously proposed formulation for the problem is non-symmetric in the sense that the corresponding linear programming relaxation bounds depend on the node selected as a root of the tree. The new formulation (the reformulation by intersection) is obtained by intersecting the feasible sets of the models corresponding to each possible root selection for the underlying directed problem. Theoretical results will show that the linear programming relaxation of the new formulation dominates the linear programming relaxation of each of the rooted formulations and is comparable with the linear programming bounds of the best formulation known for the problem. A Lagrangean relaxation scheme derived from the new formulation is also proposed and tested, with quite favourable results, on instances with up to 500 nodes and 5000 edges.     

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.     

Solving diameter‐constrained minimum spanning tree problems by constraint programming

The diameter‐constrained minimum spanning tree problem consists in finding a minimum spanning tree of a given graph, subject to the constraint that the maximum number of edges between any two vertices in the tree is bounded from above by a given constant. This problem typically models network design applications where all vertices communicate with each other at a minimum cost, subject to a given quality requirement. We propose alternative formulations using constraint programming that circumvent weak lower bounds yielded by most mixed‐integer programming formulations. Computational results show that the proposed formulation, combined with an appropriate search procedure, solves larger instances and is faster than other approaches in the literature.     

Exact algorithms for OWA-optimization in multiobjective spanning tree problems

This paper deals with the multiobjective version of the optimal spanning tree problem. More precisely, we are interested in determining the optimal spanning tree according to an Ordered Weighted Average (OWA) of its objective values. We first show that the problem is weakly NP-hard. We then propose different mixed integer programming formulations, according to different subclasses of OWA functions. Furthermore, we provide various preprocessing procedures, the validity scopes of which depend again on the considered subclass of OWA functions. For designing such procedures, we propose generalized optimality conditions and efficiently computable bounds. These procedures enable to reduce the size of the instances before launching an off-the-shelf software for solving the mixed integer program. Their impact on the resolution time is evaluated on the basis of numerical experiments.     

Exact and heuristic procedures for single machine scheduling with quadratic earliness and tardiness penalties

The present paper studies the single machine, no-idle-time scheduling problem with a weighted quadratic earliness and tardiness objective. We investigate the relationship between this problem and the assignment problem, and we derive two lower bounds and several heuristic procedures based on this relationship. Furthermore, the applicability of the time-indexed integer programming formulation is investigated. The results of a computational experiment on a set of randomly generated instances show (1) the high-quality results of the proposed heuristics, (2) the low optimality gap of one of the proposed lower bounds and (3) the applicability of the integer programming formulation to small and medium size cases of the problem.     

A note on “event-based MILP models for resource-constrained project scheduling problems”

Recently, new mixed integer linear programming formulations for the resource-constrained project scheduling problem were proposed by Koné et al. [3]. Unfortunately, the presentation of the first new model (called start/end-based formulation SEE) was not correct. More precisely, a set of necessary constraints representing the relative positioning of start and end events of activities was unintentionally omitted in the paper although it was present in the integer program used for the computational experiments. After presenting a counterexample showing the incorrectness, we provide a disaggregated and an aggregated variant of the set of necessary constraints, the disaggregated formulation yielding in theory a better linear programming relaxation. We present computational results showing that although the linear programming relaxations of both formulations yield equivalently poor lower bounds, the disaggregated formulation shows in average a better performance for integer solving of a well-known set of 30-activity instances.     

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.     

Optimized load planning for motorail transportation

This paper studies a real-world problem arising in the area of motorail transportation. The considered problem deals with the loading of cars and motorcycles onto motorail wagons under realistic technical and legal constraints. The load planning problem, introduced as motorail transportation problem (MTP), occurs during the booking process and afterwards during the loading process at motorail terminals. Optimization based decision support is highly valuable due to the combinatorial nature of these problems. In practical applications, the fast generation of good solutions is essential. Previous model formulations in literature reveal considerable optimality gaps in real-world instances. Hence, we propose and evaluate two novel integer linear programming formulations of the MTP. The first formulation is a simplified reformulation of the original problem, uses less variables and provides a tighter LP relaxation. The second model is a column-generation formulation of the reformulated model which is solved using branch-and-price. Both novel model formulations are compared and evaluated on the basis of real-world data sets and considerably outperform previous approaches in terms of solution quality and speed.     

Min-degree constrained minimum spanning tree problem with fixed centrals and terminals: Complexity,properties and formulations

We consider a variant of the Min-Degree Constrained Minimum Spanning Tree Problem where the central and terminal nodes are fixed a priori. We prove that the optimization problem is NP-Hard even for complete graphs and the feasibility problem is NP-Complete even if there is an edge between each central and each terminal in the input graph. Actually, this complexity result still holds when the minimum degree of each central node is restricted to be a same value d ≥ 2. We derive necessary and sufficient conditions for feasibility. We present several integer linear programming formulations – based on known formulations for the minimum spanning tree problem – along with a theoretical comparison among the lower bounds provided by their linear relaxations. We propose three Lagrangian heuristics. Computational experiments compare the performances of the heuristics and the formulations.     

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.     

Weighted and unweighted maximum clique algorithms with upper bounds from fractional coloring

The linear programming relaxation of the minimum vertex coloring problem, called the fractional coloring problem, is NP-hard. We describe efficient approximation procedures for both the weighted and unweighted versions of the problem. These fractional coloring procedures are then used for generating upper bounds for the (weighted or unweighted) maximum clique problem in the framework of a branch-and-bound procedure. Extensive computational testing shows that replacing the standard upper bounding procedures based on various integer coloring heuristics with the somewhat more expensive fractional coloring procedure results in improvements of the bound by up to one-fourth in the unweighted and up to one-fifth in the weighted case, accompanied by a decrease in the size of the search tree by a factor of almost two.This research was supported by the National Science Foundation under Grant No. DDM-9201340 and the Office of Naval Research through Contract N00014-85-K-0198.     

Tight bounds from a path based formulation for the tree of hub location problem

This paper considers the tree of hub location problem. We propose a four index formulation which yields much tighter LP bounds than previously proposed formulations, although at a considerable increase of the computational burden when obtained with a commercial solver. For this reason we propose a Lagrangean relaxation, based on the four index formulation, that exploits the structure of the problem by decomposing it into independent subproblems which can be solved quite efficiently. We also obtain upper bounds by means of a simple heuristic that is applied at the inner iterations of the method that solves the Lagrangean dual. As a consequence, the proposed Lagrangean relaxation produces tight upper and lower bounds and enable us to address instances up to 100 nodes, which are notably larger than the ones previously considered in the literature, with sizes up to 20 nodes. Computational experiments have been performed with benchmark instances from the literature. The obtained results are remarkable. For most of the tested instances we obtain or improve the best known solution and for all tested instances the deviation between our upper and lower bounds, never exceeds 10%.     

Formulations and relaxations for a multi-echelon capacitated location–distribution problem

We consider a multi-echelon location–distribution problem arising from an actual application in fast delivery service. We present and compare two formulations for this problem: an arc-based model and a path-based model. We show that the linear programming (LP) relaxation of the path-based model provides a better bound than the LP relaxation of the arc-based model. We also compare the so-called binary relaxations of the models, which are obtained by relaxing the integrality constraints for the general integer variables, but not for the 0–1 variables. We show that the binary relaxations of the two models always provide the same bound, but that the path-based binary relaxation appears preferable from a computational point of view, since it can be reformulated as an equivalent simple plant location problem (SPLP), for which several efficient algorithms exist. We also show that the LP relaxation of this SPLP reformulation provides a better bound than the LP relaxation of the path-based model.     

Lift-Gas Allocation Under Precedence Constraints: MILP Formulation and Computational Analysis

The distribution of a limited rate of high-pressure gas to gas-lifted wells, while respecting injection bounds and activation precedence constraints, consists of a mixed-integer nonlinear programming problem. This paper proposes a mixed-integer linear formulation obtained by piecewise-linearizing the nonlinear functions, thereby allowing the use of integer programming algorithms. Valid inequalities for the convex hull of feasible solutions are derived from knapsack covers, for which exact and approximate lifting procedures yield stronger inequalities. Numerical results show that these cover-based cuts reduce the number of nodes explored in a branch-and-bound search.      

Scheduling jobs on a single batch processing machine with incompatible job families and weighted number of tardy jobs objective

In this paper, we minimize the weighted and unweighted number of tardy jobs on a single batch processing machine with incompatible job families. We propose two different mixed integer linear programming (MILP) formulations based on positional variables. The second formulation does not contain a big-M coefficient. Two iterative schemes are discussed that are able to provide tighter linear programming bounds by reducing the number of positional variables. Furthermore, we also suggest a random key genetic algorithm (RKGA) to solve this scheduling problem. Results of computational experiments are shown. The second MILP formulation is more efficient with respect to lower bounds, while the first formulation provides better upper bounds. The iterative scheme is effective for the weighted case. The RKGA is able to find high-quality solutions in a reasonable amount of time.     

Improved integer programming models for simple assembly line balancing and related problems

We propose a stronger formulation of the precedence constraints and the station limits for the simple assembly line balancing problem. The linear relaxation of the improved integer program theoretically dominates all previous formulations using impulse variables, and produces solutions of significantly better quality in practice. The improved formulation can be used to strengthen related problems with similar restrictions. We demonstrate their effectiveness on the U‐shaped assembly line balancing problem and on the bin packing problem with precedence constraints.     

Binary integer programming formulation and heuristics for differentiated coverage in heterogeneous sensor networks

Coverage is a fundamental task in sensor networks. We consider the minimum cost point coverage problem and formulate a binary integer linear programming model for effective sensor placement on a grid-structured sensor field when there are multiple types of sensors with varying sensing quality and price. The formulation is general and can be adapted to handle situations where sensing is perfect, imperfect or uncertain, and the coverage requirements are differentiated. Unfortunately, the new model suffers from the intractability of the binary integer programming formulations. We therefore suggest approximation algorithms and heuristics. Computational results indicate that the heuristic based on Lagrangean relaxation outperforms the others in terms of solution quality.     

Finding Outbreak Trees in Networks with Limited Information

Real-time control of infectious disease outbreaks represents one of the greatest epidemiological challenges currently faced. In this paper we address the problem of identifying contagion patterns responsible for the spread of a disease in a network, which can be applied in real-time to evaluate an ongoing outbreak. We focus on the scenario where limited information, i.e. infection reports which may or may not include the actual source, is available during an ongoing outbreak and we seek the most likely infection tree that spans at least a set of known infected nodes. This problem can be represented using a maximum likelihood constrained Steiner tree model where the objective is to find a spanning tree with an assignment of integer nodes weights. We propose a novel formulation and solution method based on a two-step heuristic which (1) reduces the initial graph using a polynomial time algorithm designed to find feasible infection paths and (2) solves an exact mixed integer linear programming reformulation of the maximum likelihood model on the resulting subgraph. The proposed methodology can be applied to outbreaks which may evolve from multiple sources. Simulated contagion episodes are used to evaluate the performance of our solution method. Our results show that the approach is computationally efficient and is able to reconstruct a significant proportion of the outbreak, even in the context of low levels of information availability.