A Benders decomposition approach for a distribution network design problem with consolidation and capacity considerations

We develop a model for a strategic freight-forwarding network design problem in which the design decisions involve the locations and capacities of consolidation and deconsolidation centers, and capacities on linehaul linkages as well as the shipment routes from origins to destinations through centers. We devise a solution approach based on Benders decomposition and conduct a computational study that illustrates the efficiency and the effectiveness of the approach.     

A partitioning algorithm for the multicommodity network flow problem

A partitioning algorithm for solving the general minimum cost multicommodity flow problem for directed graphs is presented in the framework of a network flow method and the dual simplex method. A working basis which is considerably smaller than the number of capacitated arcs in the given network is employed and a set of simple secondary constraints is periodically examined. Some computational aspects and preliminary experimental results are discussed.     

An improved Benders decomposition algorithm for the tree of hubs location problem

The tree of hubs location problem is a particularly hard variant of the so called hub location problems. When solving this problem by a Benders decomposition approach, it is necessary to deal with both optimality and feasibility cuts. While modern implementations of the Benders decomposition method rely on Pareto-optimal optimality cuts or on rendering feasibility cuts based on minimal infeasible subsystems, a new cut selection scheme is devised here under the guiding principle of extracting useful information even when facing infeasible subproblems. The proposed algorithm outperforms two other modern variants of the method and it is capable of optimally solving instances five times larger than the ones previously reported on the literature.     

A memetic algorithm approach for solving the multidimensional multi-way number partitioning problem

In this paper, we describe a generalization of the multidimensional two-way number partitioning problem (MDTWNPP) where a set of vectors has to be partitioned into p sets (parts) such that the sums per every coordinate should be exactly or approximately equal. We will call this generalization the multidimensional multi-way number partitioning problem (MDMWNPP). Also, an efficient memetic algorithm (MA) heuristic is developed to solve the multidimensional multi-way number partitioning problem obtained by combining a genetic algorithm (GA) with a powerful local search (LS) procedure. The performances of our memetic algorithm have been compared with the existing numerical results obtained by CPLEX based on an integer linear programming formulation of the problem. The solution reveals that our proposed methodology performs very well in terms of both quality of the solutions obtained and the computational time compared with the previous method of solving the multidimensional two-way number partitioning problem.     

A 2-approximation algorithm for the network substitution problem

The network substitution problem is to substitute an existing network for a new network so that to minimize the cost of exploiting the existing network during the period when the new network is being constructed. We show that this problem is NP-hard, and propose a 2-approximation algorithm for solving it.     

Contribution of copositive formulations to the graph partitioning problem

This article provides analysis of several copositive formulations of the graph partitioning problem and semidefinite relaxations based on them. We prove that the copositive formulations based on results from Burer [S. Burer, On the copositive representation of binary and continuous nonconvex quadratic programs. Math. Program. 120 (Ser. A) (2009), pp. 479–495] and the author of the paper [J. Povh, Semidefinite approximations for quadratic programs over orthogonal matrices. J. Global Optim. 48 (2010), pp. 447–463] are equivalent and that they both imply semidefinite relaxations which are stronger than the Donath–Hoffman eigenvalue lower bound [W.E. Donath and A.J. Hoffman, Lower bounds for the partitioning of graphs. IBM J. Res. Develop. 17 (1973), pp. 420–425] and the projected semidefinite lower bound from Wolkowicz and Zhao [H. Wolkowicz and Q. Zhao, Semidefinite programming relaxations for the graph partitioning problem. Discrete Appl. Math. 96–97 (1999), pp. 461–479].     

A heuristic for the container loading problem: A tertiary-tree-based dynamic space decomposition approach

Increasing fuel costs, post-911 security concerns, and economic globalization provide a strong incentive for container carriers to use available container space more efficiently, thereby minimizing the number of container trips and reducing socio-economic vulnerability. A heuristic algorithm based on a tertiary tree model is proposed to handle the container loading problem (CLP) with weakly heterogeneous boxes. A dynamic space decomposition method based on the tertiary tree structure is developed to partition the remaining container space after a block of homogeneous rectangular boxes is loaded into a container. This decomposition approach, together with an optimal-fitting sequencing and an inner-right-corner-occupying placement rule, permits a holistic loading strategy to pack a container. Comparative studies with existing algorithms and an illustrative example demonstrate the efficiency of this algorithm.     

A specialized network simplex algorithm for the constrained maximum flow problem

The constrained maximum flow problem is to send the maximum flow from a source to a sink in a directed capacitated network where each arc has a cost and the total cost of the flow cannot exceed a budget. This problem is similar to some variants of classical problems such as the constrained shortest path problem, constrained transportation problem, or constrained assignment problem, all of which have important applications in practice. The constrained maximum flow problem itself has important applications, such as in logistics, telecommunications and computer networks. In this research, we present an efficient specialized network simplex algorithm that significantly outperforms the two widely used LP solvers: CPLEX and lp_solve. We report CPU times of an average of 27 times faster than CPLEX (with its dual simplex algorithm), the closest competitor of our algorithm.     

A prototype column generation strategy for the multiple container loading problem

The multiple container loading cost minimization problem (MCLCMP) is a practical and useful problem in the transportation industry, where products of various dimensions are to be loaded into containers of various sizes so as to minimize the total shipping cost. The MCLCMP can be naturally formulated as a set cover problem and solved using column generation techniques, which is a popular method for handling huge numbers of variables. However, the direct application of column generation is not effective because feasible solutions to the pricing subproblem is required, which for the MCLCMP is NP-hard. We show that efficiency can be greatly improved by generating prototypes that approximate feasible solutions to the pricing problem rather than actual columns. For many hard combinatorial problems, the subproblem in column generation based algorithms is NP-hard; if suitable prototypes can be quickly generated that approximate feasible solutions, then our strategy can also be applied to speed up these algorithms.     

A tree search method for the container loading problem with shipment priority

This paper addresses a special kind of container loading problem with shipment priority. We present a tree search method, which is based on a greedy heuristic. In the greedy heuristic, blocks made up of identical items with the same orientation are selected for packing into a container. Five evaluation functions are proposed for block selection, and the different blocks selected by each evaluation function constitute the branches of the search tree. A method of space splitting and merging is also embedded in the algorithm to facilitate efficient use of the container space. In addition, the proposed algorithm covers an important constraint called shipment priority to solve practical problems. The validity of the proposed algorithm is examined by comparing the present results with those of published algorithms using the same data.     

Performance of a genetic algorithm for the graph partitioning problem

The performance of the genetic algorithm (GA) for the graph partitioning problem (GPP) is investigated by comparison with standard heuristics on well-known benchmark graphs. In general, there is a case where a practical performance of a conventional genetic approach, which performs only simple operations without a local search strategy, is not sufficient. However, it is known that a combination of GA and local search can produce better solutions. From this practice, we incorporate a simple local search algorithm into the GA. In particular, the search ability of the GA is compared with standard heuristics such as multistart local search and simulated annealing, which use the same neighborhood structure of the simple local search, for solving the GPP. Experimental results show that the GA performs better than its competitors.     

Penalty computations for the set partitioning problem

The computation of penalties associated with the continuous relaxation of integer programming problems can be useful to derive conditional and relational tests which allow to fix some variables at their optimal value or to generate new constraints (cuts). We study in this paper the computation and the use of penalties as a tool to improve the efficiency of algorithms for solving set partitioning problems. This leads to a preprocessing scheme which can be embedded within any exact or approximate algorithm. The strength of these penalties is illustrated through computational results on some real-world set partitioning problems.This work was sponsored by FINEP (research contract number 4.3.86.0689-00), CNPq (research contract numbers 11.1592-84, 30.2281-85 and 40.2002-86.5), IBM Brazil and NSERC (grant # GP0036426).On leave from the Catholic University of Rio de Janeiro, Department of Electrical Engineering, Caixa Postal 38063, Gávea, Rio de Janeiro 22452, Brazil.     

A strongly polynomial algorithm for the minimum maximum flow degree problem

Let us consider a network flow respecting arc capacities and flow conservation constraints. The flow degree of a node is sum of the flow entering and leaving it. We study the problem of determining a flow that minimizes the maximum flow degree of a node. We show how to solve it in strongly polynomial time with linear programming.     

A capacity scaling heuristic for the multicommodity capacitated network design problem

In this paper, we propose a capacity scaling heuristic using a column generation and row generation technique to address the multicommodity capacitated network design problem. The capacity scaling heuristic is an approximate iterative solution method for capacitated network problems based on changing arc capacities, which depend on flow volumes on the arcs. By combining a column and row generation technique and a strong formulation including forcing constraints, this heuristic derives high quality results, and computational effort can be reduced considerably. The capacity scaling heuristic offers one of the best current results among approximate solution algorithms designed to address the multicommodity capacitated network design problem.     

A network model for airline cabin crew scheduling

Airline crew scheduling problems have been traditionally formulated as set covering problems or set partitioning problems. When flight networks are extended, these problems become more complicated and thus more difficult to solve. From the current practices of a Taiwan airline, whose work rules are relatively simple compared to many airlines in other countries, we find that pure network models, in addition to traditional set covering (partitioning) problems, can be used to formulate their crew scheduling problems. In this paper, we introduce a pure network model that can both efficiently and effectively solve crew scheduling problems for a Taiwan airline using real constraints. To evaluate the model, we perform computational tests concerning the international line operations of a Taiwan airline.     

An integrated model for logistics network design

In this paper we introduce a new formulation of the logistics network design problem encountered in deterministic, single-country, single-period contexts. Our formulation is flexible and integrates location and capacity choices for plants and warehouses with supplier and transportation mode selection, product range assignment and product flows. We next describe two approaches for solving the problem---a simplex-based branch-and-bound and a Benders decomposition approach. We then propose valid inequalities to strengthen the LP relaxation of the model and improve both algorithms. The computational experiments we conducted on realistic randomly generated data sets show that Benders decomposition is somewhat more advantageous on the more difficult problems. They also highlight the considerable performance improvement that the valid inequalities produce in both solution methods. Furthermore, when these constraints are incorporated in the Benders decomposition algorithm, this offers outstanding reoptimization capabilities.     

Noising methods for a clique partitioning problem

This paper deals with the application of noising methods to a clique partitioning problem for a weighted graph. The aim is to study different ways to add noise to the data, and to show that the choice of the noise-adding-scheme may have some impact on the performance of these methods. Among the noise-adding-schemes described here, two of them are totally new, leading to the “forgotten vertices” and to the “forgotten edges” methods. We also experimentally study a generic noising method that automatically tunes its parameters. For each noise-adding-scheme, we compare a variant which inserts descents and a variant which does not.     

A MIP-based approach to solve the prize-collecting local access network design problem

This paper presents a new combinatorial optimization problem that can be used to model the deployment of broadband telecommunications systems in which optical fiber cables are installed between a central office and a number of end-customers. In this capacitated network design problem the installation of optical fiber cables with sufficient capacity is required to carry the traffic from the central office to the end-customers at minimum cost. In the situation motivating this research the network does not necessarily need to connect all customers (or at least not with the best available technology). Instead, some nodes are potential customers. The aim is to select the customers to be connected to the central server and to choose the cable capacities to establish these connections. The telecom company takes the strategic decision of fixing a percentage of customers that should be served, and aims for minimizing the total cost of the network providing this minimum service. For that reason the underlying problem is called the Prize-Collecting Local Access Network Design problem (PC-LAN).     

An efficient approximation algorithm for the survivable network design problem

The survivable network design problem (SNDP) is to construct a minimum-cost subgraph satisfying certain given edge-connectivity requirements. The first polynomial-time approximation algorithm was given by Williamson et al. (Combinatorica 15 (1995) 435–454). This paper gives an improved version that is more efficient. Consider a graph ofn vertices and connectivity requirements that are at mostk. Both algorithms find a solution that is within a factor 2k – 1 of optimal fork 2 and a factor 2 of optimal fork = 1. Our algorithm improves the time from O(k ³n⁴) to O ). Our algorithm shares features with those of Williamson et al. (Combinatorica 15 (1995) 435–454) but also differs from it at a high level, necessitating a different analysis of correctness and accuracy; our analysis is based on a combinatorial characterization of the redundant edges. Several other ideas are introduced to gain efficiency. These include a generalization of Padberg and Rao's characterization of minimum odd cuts, use of a representation of all minimum (s, t) cuts in a network, and a new priority queue system. The latter also improves the efficiency of the approximation algorithm of Goemans and Williamson (SIAM Journal on Computing 24 (1995) 296–317) for constrained forest problems such as minimum-weight matching, generalized Steiner trees and others. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.A preliminary version of this paper has appeared in the Proceedings of the Third Mathematical Programming Society Conference on Integer Programming and Combinatorial Optimization, 1993, pp. 57–74.Research supported in part by NSF Grant No. CCR-9215199 and AT & T Bell Laboratories.Research supported in part by Air Force contracts AFOSR-89-0271 and F49620-92-J-0125 and DARPA contracts N00014-89-J-1988 and N00014-92-1799.This research was performed while the author was a graduate student at MIT. Research supported by an NSF Graduate Fellowship, Air Force contract F49620-92-J-0125, DARPA contracts N00014-89-J-1988 and N00014-92-J-1799, and AT & T Bell Laboratories.