Zero-one integer programs with few constraints —Lower bounding theory

The zero-one integer programming problem and its special case, the multiconstraint knapsack problem frequently appear as subproblems in many combinatorial optimization problems. We present several methods for computing lower bounds on the optimal solution of the zero-one integer programming problem. They include Lagrangean, surrogate and composite relaxations. New heuristic procedures are suggested for determining good surrogate multipliers. Based on theoretical results and extensive computational testing, it is shown that for zero-one integer problems with few constraints surrogate relaxation is a viable alternative to the commonly used Lagrangean and linear programming relaxations. These results are used in a follow up paper to develop an efficient branch and bound algorithm for solving zero-one integer programming problems.     

Optimal infrastructure design and expansion of broadband wireless access networks

This paper investigates the important infrastructure design and expansion problem for broadband wireless access networks subject to user demand constraints and system capacity constraints. For the problem, an integer program is derived and a heuristic solution procedure is proposed based on Lagrangean relaxation. In the computational experiments, our Lagrangean relaxation based algorithm can solve this complex design and expansion problem quickly and near optimally. Based on the test results, it is suggested that the proposed algorithm may be practically used for the infrastructure design and expansion problem for broadband wireless access networks.     

Capacity planning for phased implementation of flexible manufacturing systems under budget restrictions

We consider a problem of gradually replacing conventional dedicated machines with flexible manufacturing modules (FMMs) under budget restrictions over a finite planning horizon assuming that dedicated machines cannot be purchased during the planning horizon and acquired FMMs are kept until the end of the horizon. In the problem, a replacement schedule is to be determined and operations are to be assigned to the FMMs or the dedicated machines with the objective of minimizing the sum of discounted costs of acquisition and operation of FMMs and operation costs of conventional dedicated machines. In this research, the problem is formulated as a mixed integer linear program and solved by a Lagrangean relaxation approach. A subgradient optimization method is employed to obtain lower bounds of solutions and a multiplier adjustment method is devised to improve the lower bounds. We develop a linear programming-based Lagrangean heuristic algorithm to find a good feasible solution of the original problem in a reasonable amount of computation time. The algorithm is tested on randomly generated test problems and the results are reported.     

Fixed Charge Transportation Problems: a new heuristic approach based on Lagrangean relaxation and?the?solving of core problems

In this paper the Fixed Charge Transportation Problem is considered. A new heuristic approach is proposed, based on the intensive use of Lagrangean relaxation techniques. The more novel aspects of this approach are new Lagrangean relaxation and decomposition methods, the consideration of several core problems, defined from the previously computed Lagrangean reduced costs, the heuristic selection of the most promising core problem and the final resort to enumeration by applying a branch and cut algorithm to the selected core problem. For problems with a small ratio of the average fixed cost to the average variable cost (lower than or equal to 25), the proposed method can obtain similar or better solutions than the state-of-art algorithms, such as the tabu search procedure and the parametric ghost image processes. For larger ratios (between 50 and 180), the quality of the obtained solutions could be considered to be halfway between both methods.     

Lagrangean relaxation

This paper reviews some of the most intriguing results and questions related to Lagrangean relaxation. It recalls essential properties of the Lagrangean relaxation and of the Lagrangean function, describes several algorithms to solve the Lagrangean dual problem, and considers Lagrangean heuristics, ad-hoc or generic, because these are an integral part of any Lagrangean approximation scheme. It discusses schemes that can potentially improve the Lagrangean relaxation bound, and describes several applications of Lagrangean relaxation, which demonstrate the flexibility of the approach, and permit either the computation of strong bounds on the optimal value of the MIP problem, or the use of a Lagrangean heuristic, possibly followed by an iterative improvement heuristic. The paper also analyzes several interesting questions, such as why it is sometimes possible to get a strong bound by solving simple problems, and why an a-priori weaker relaxation can sometimes be “just as good” as an a-priori stronger one.     

Lagrangean relaxation based heuristics for lot sizing with setup times

We consider a lot sizing problem with setup times where the objective is to minimize the total inventory carrying cost only. The demand is dynamic over time and there is a single resource of limited capacity. We show that the approaches implemented in the literature for more general versions of the problem do not perform well in this case. We examine the Lagrangean relaxation (LR) of demand constraints in a strong reformulation of the problem. We then design a primal heuristic to generate upper bounds and combine it with the LR problem within a subgradient optimization procedure. We also develop a simple branch and bound heuristic to solve the problem. Computational results on test problems taken from the literature show that our relaxation procedure produces consistently better solutions than the previously developed heuristics in the literature.     

A Lagrangean relaxation heuristic for vehicle routing

This paper presents a new heuristic algorithm for the vehicle routing problem (VRP) which makes use of Lagrangean relaxation to transform the VRP into a modified m-traveling salesman problem. Application of the proposed algorithm to test problems from the literature has produced new best-known solutions.     

A branch and bound algorithm for the symmetric traveling salesman problem based on the 1-tree relaxation

In 1970 Held and Karp introduced the Lagrangean approach to the symmetric traveling salesman problem. We use this 1-tree relaxation in a new branch and bound algorithm. It differs from other algorithms not only in the branching scheme, but also in the ascent method to calculate the 1-tree bounds. urthermore we determine heuristic solutions throughout the computations to provide upperbounds. We present computational results for both a depth-first and a breadth-first version of our algorithm. On the average our results on a number of Euclidean problems from the literature are obtained in about 60% less 1-trees than the best known algorithm based on the 1-tree relaxation. For random table problems (up to 100 cities) the average results are also satisfactory.     

Optimal routing in non-geostationary satellite ATM networks with intersatellite link capacity constraints

The trend toward broadband communications in space is foreseeable, and its features predestine ATM as the basic mode of operation. Some of the low and medium earth orbit satellite concepts make use of intersatellite links (ISLs) to provide global connectivity with minimal usage of terrestrial fixed network resources. Interconnecting neighbouring satellites with ISLs results in a partially meshed switching subnetwork in space. The ISLs have a time-varying distance or may even lose sight of each other. This feature of the ISL topology dynamics significantly increases the complexity of connection-oriented network operation and routing. We deal with the routing problem to minimize the virtual path connection handover rate and path delay in the time-varying ISL subnetwork topology with ISL capacity constraints. A heuristic algorithm is proposed to deal with this problem, which is based on Lagrangean relaxation and dynamic programming. When there is sufficient capacity at every ISL, the algorithm produces an optimal solution easily using only dynamic programming. For evaluation of our algorithm, some computational results have been presented. These results show that our optimization algorithm can produce a solution close to an optimal solution when there exist ISL capacity constraints.     

An effective heuristic for large-scale capacitated facility location problems

The Capacitated Facility Location Problem (CFLP) consists of locating a set of facilities with capacity constraints to satisfy the demands of a set of clients at the minimum cost. In this paper we propose a simple and effective heuristic for large-scale instances of CFLP. The heuristic is based on a Lagrangean relaxation which is used to select a subset of “promising” variables forming the core problem and on a Branch-and-Cut algorithm that solves the core problem. Computational results on very large scale instances (up to 4 million variables) are reported.     

Hierarchical design of an integrated production and 2-echelon distribution system

This study uses the method of Lagrangean relaxation in the hierarchical design of an integrated model of production–distribution functions in a 2-echelon system. A mixed integer mathematical model is developed with a centralized planning perspective to address production and distribution decisions simultaneously. In order to solve the resulting large-scale problem, the Lagrangean relaxation is used to decouple the imbedded distribution and production subproblems, and subgradient optimization is implemented to coordinate the information flow between these in a hierarchical manner. This corresponds to a decentralized organizational design where a central agent coordinates the information exchange between the distribution and production organizational units. A forward heuristic designed to solve the distribution subproblem is shown to provide good solutions. Hierarchical interdependency is incorporated into the Lagrangean heuristic such that distribution decisions are placed in the top level to restrict the solution of the production subproblem in the lower level.     

A Lagrangean heuristic algorithm for disassembly scheduling with capacity constraints

This paper considers the problem of determining the disassembly schedule (quantity and timing) of products in order to satisfy the demand of their parts or components over a finite planning horizon. The objective is to minimize the sum of set-up, disassembly operation, and inventory holding costs. As an extension of the uncapacitated versions of the problem, we consider the resource capacity restrictions over the planning horizon. An integer program is suggested to describe the problem mathematically, and to solve the problem, a heuristic is developed using a Lagrangean relaxation technique together with a method to find a good feasible solution while considering the trade-offs among different costs. The effectiveness of the algorithm is tested on a number of randomly generated problems and the test results show that the heuristic suggested in this paper can give near optimal solutions within a short amount of computation time.     

Solving capacitated facility location problems by Fenchel cutting planes

In this paper, we apply the Fenchel cutting planes methodology to Capacitated Facility Location problems. We select a suitable knapsack structure from which depth cuts can be obtained. Moreover, we simultaneously obtain a primal heuristic solution. The lower and upper bounds achieved by our procedure are compared with those provided by Lagrangean relaxation of the demand constraints. As the computational results show the Fenchel cutting planes methodology outperforms the Lagrangean one, both in the obtaining of the bounds and in the effectiveness of the branch and bound algorithm using each relaxation as the initial formulation.     

An Optimization Problem with a Separable Non-Convex Objective Function and a Linear Constraint

For a class of global optimization (maximization) problems, with a separable non-concave objective function and a linear constraint a computationally efficient heuristic has been developed.The concave relaxation of a global optimization problem is introduced. An algorithm for solving this problem to optimality is presented. The optimal solution of the relaxation problem is shown to provide an upper bound for the optimal value of the objective function of the original global optimization problem. An easily checked sufficient optimality condition is formulated under which the optimal solution of concave relaxation problem is optimal for the corresponding non-concave problem. An heuristic algorithm for solving the considered global optimization problem is developed.The considered global optimization problem models a wide class of optimal distribution of a unidimensional resource over subsystems to provide maximum total output in a multicomponent systems.In the presented computational experiments the developed heuristic algorithm generated solutions, which either met optimality conditions or had objective function values with a negligible deviation from optimality (less than 1/10 of a percent over entire range of problems tested).     

A Lagrangean dual ascent algorithm for simple plant location problems

We propose to strengthen the separable Lagrangean relaxation of the Simple Plant Location Problem (SPLP) by using Benders inequalities generated during a Lagrangean dual ascent procedure. These inequalities are expressed in terms of the 0–1 variables only, and they can be used as knapsack constraints in the pure integer part of the Lagrangean relaxation. We show how coupling this technique with a good primal heuristic can substantially reduce integrality gaps.     

A Lagrangean heuristic for the maximal covering location problem

We develop a Lagrangean heuristic for the maximal covering location problem. Upper bounds are given by a vertex addition and substitution heuristic and lower bounds are produced through a subgradient optimization algorithm. The procedure was tested in networks of up to 150 vertices. A duality gap was generally present at the end of the heuristic for the larger problems. The test problems were run in an IBM 3090-600J ‘super-computer’; the maximum computing time was kept below three minutes of CPU.     

A branch-and-price algorithm for the capacitated facility location problem

The capacitated facility location problem (CFLP) is a well-known combinatorial optimization problem with applications in distribution and production planning. It consists in selecting plant sites from a finite set of potential sites and in allocating customer demands in such a way as to minimize operating and transportation costs. A number of solution approaches based on Lagrangean relaxation and subgradient optimization has been proposed for this problem. Subgradient optimization does not provide a primal (fractional) optimal solution to the corresponding master problem. However, in order to compute optimal solutions to large or difficult problem instances by means of a branch-and-bound procedure information about such a primal fractional solution can be advantageous. In this paper, a (stabilized) column generation method is, therefore, employed in order to solve a corresponding master problem exactly. The column generation procedure is then employed within a branch-and-price algorithm for computing optimal solutions to the CFLP. Computational results are reported for a set of larger and difficult problem instances.     

An Improved Algorithm for the Capacitated Facility Location Problem

In this paper we consider the classical capacitated facility location problem. A branch and bound algorithm is presented which measurably improves upon the recent results of Akinc and Khumawala. The use of a specialized Lagrangean relaxation results in significantly tighter bounds than those for the traditional continuous relaxation. These bounds, when combined with penalties derived from the Lagrangean relaxation, enable many integer variables to be fixed at specific values. This results in fewer branches, and indeed for certain test problems taken from the literature, branching is not required. Average computation time for a battery of test problems from the literature has been reduced (conservatively) by a factor of 3.     

On the resolution of the single product capacitated machine siting problem

The single product capacitated machine siting problem (SPCMSP) is an extension of the simple plant location problem, in which plant production depends on installing capacitated machines. In this paper we compare, both theoretically and computationally, three heuristic algorithms for the SPCMSP based upon Lagrangean relaxation and reduction tests of a mixed-integer formulation of the problem, which is NP-hard. We test the performance of the algorithms with examples involving up to 100 potential plants, 1000 customers and six potential machines per plant, which we obtain encouraging results.     

An Algorithm for the Design of Multitype Concentrator Networks

In recent years we have witnessed remarkable progress in the development of the topological design of computer communication networks. One of the important aspects of the topological design of computer communication networks is the concentrator location problem. This problem is a complex combinatorial problem that belongs to the difficult class of NP-complete problems where the computation of an optimal solution is still a challenging task. This paper extends the standard capacitated concentrator location problem to a generalization of multitype capacitated concentrator location problems and presents an efficient algorithm based on cross decomposition. This algorithm incorporates the Benders decomposition and Lagrangean relaxation methods into a single framework and exploits the resulting primal and dual structure simultaneously. Computational results are quite satisfactory and encouraging and show this algorithm to be both efficient and effective. The use of cross decomposition as a heuristic algorithm is also discussed.