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.     

A Slope Scaling/Lagrangean Perturbation Heuristic with Long-Term Memory for Multicommodity Capacitated Fixed-Charge Network Design

This paper describes a slope scaling heuristic for solving the multicomodity capacitated fixed-charge network design problem. The heuristic integrates a Lagrangean perturbation scheme and intensification/diversification mechanisms based on a long-term memory. Although the impact of the Lagrangean perturbation mechanism on the performance of the method is minor, the intensification/diversification components of the algorithm are essential for the approach to achieve good performance. The computational results on a large set of randomly generated instances from the literature show that the proposed method is competitive with the best known heuristic approaches for the problem. Moreover, it generally provides better solutions on larger, more difficult, instances.     

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.     

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 decomposition: A model yielding stronger lagrangean bounds

Given a mixed-integer programming problem with two matrix constraints, it is possible to define a Lagrangean relaxation such that the relaxed problem decomposes additively into two subproblems, each having one of the two matrices of the original problem as its constraints. There is one Lagrangean multiplier per variable. We prove that the optimal value of this new Lagrangean dual dominates the optimal value of the Lagrangean dual obtained by relaxing one set of constraints and give a necessary condition for a strict improvement. We show on an example that the resulting bound improvement can be substantial. We show on a complex practical problem how Lagrangean decomposition may help uncover hidden special structures and thus yield better solution methodology. Research supported by the National Science Foundation under grant ECS-8508142.     

Lagrangean variables in infinite dimensional spaces for a dynamic economic equilibrium problem

This paper is focused on the study of a dynamic competitive equilibrium by using Lagrangean multipliers. This mathematical formulation allows us the improve the Walrasian model by considering the common possibility of an uncharged delayed payment in a given time (for example, by using a credit card). Firstly the economic equilibrium problem is reformulated as an evolutionary variational problem; then the Lagrangean theory in infinite dimensional spaces is applied. Thanks to the application of this theory we obtain the existence of Lagrangean multipliers, which allows us to give a computational procedure for the equilibrium solutions.     

Lagrangean/surrogate relaxation for generalized assignment problems

This work presents Lagrangean/surrogate relaxation to the problem of maximum profit assignment of n tasks to m agents (n > m), such that each task is assigned to only one agent subject to capacity constraints on the agents. The Lagrangean/surrogate relaxation combines usual Lagrangean and surrogate relaxations relaxing first a set of constraints in the surrogate way. Then, the Lagrangean relaxation of the surrogate constraint is obtained and approximately optimized (one-dimensional dual). The Lagrangean/surrogate is compared with the usual Lagrangean relaxation on a computational study using a large set of instances. The dual bounds are the same for both relaxations, but the Lagrangean/surrogate can give improved local bounds at the application of a subgradient method, resulting in less computational times. Three relaxations are derived for the problem. The first relaxation considers a vector of multipliers for the capacity constraints, the second for the assignment constraints and the other for the Lagrangean decomposition constraints. Relaxation multipliers are used with efficient constructive heuristics to find good feasible solutions. The application of a Lagrangean/surrogate approach seems very promising for large scale problems.     

A new Lagrangean approach to the pooling problem

We present a new Lagrangean approach for the pooling problem. The relaxation targets all nonlinear constraints, and results in a Lagrangean subproblem with a nonlinear objective function and linear constraints, that is reformulated as a linear mixed integer program. Besides being used to generate lower bounds, the subproblem solutions are exploited within Lagrangean heuristics to find feasible solutions. Valid cuts, derived from bilinear terms, are added to the subproblem to strengthen the Lagrangean bound and improve the quality of feasible solutions. The procedure is tested on a benchmark set of fifteen problems from the literature. The proposed bounds are found to outperform or equal earlier bounds from the literature on 14 out of 15 tested problems. Similarly, the Lagrangean heuristics outperform the VNS and MALT heuristics on 4 instances. Furthermore, the Lagrangean lower bound is equal to the global optimum for nine problems, and on average is 2.1% from the optimum. The Lagrangean heuristics, on the other hand, find the global solution for ten problems and on average are 0.043% from the optimum.     

Ranking lower bounds for the bin-packing problem

In this paper, we evaluate different known lower bounds for the bin-packing problem including linear programming relaxation (LP), Lagrangean relaxation (LR), Lagrangean decomposition (LD) and the Martello–Toth (MT) [Martello, S., Toth, P., Knapsack Problems: Algorithms and Computer Implementations, Wiley, New York, 1990] lower bounds. We give conditions under which Lagrangean bounds are superior to the LP bound, show that Lagrangean decomposition (LD) yields the same bound as Lagrangean relaxation (LR) and prove that the MT lower bound is a Lagrangean bound evaluated at a finite set of Lagrange multipliers; hence, it is no better than the LR and LD lower bounds.     

Selection of Capacity Expansion Projects

The problem of determining a project selection schedule and a production-distribution-inventory schedule for each of a number of plants so as to meet the demands of multiregional markets at minimum discounted total cost during a discrete finite planning horizon is considered. We include the possibility of using inventory and/or imports to delay the expansion decision at each producing region in a transportation network. Through a problem reduction algorithm, the Lagrangean relaxation problem strengthened by the addition of a surrogate constraint becomes a 0–1 mixed integer knapsack problem. Its optimal solution, given a set of Lagrangean multipliers, can be obtained by solving at most two generally smaller 0–1 pure integer knapsack problems. The bound is usually very tight. At each iteration of the subgradient method, we generate a primal feasible solution from the Lagrangean solution. The computational results indicate that the procedure is effective in solving large problems to within acceptable error tolerances.     

Calculating surrogate constraints

Various theoretical properties of the surrogate dual of a mathematical programming problem are discussed, including some connections with the Lagrangean dual. Two algorithms for solving the surrogate dual, suggested by analogy with Lagrangean optimisation, are described and proofs of their convergence given. A simple example is solved using each method.     

A technique for speeding up the solution of the Lagrangean dual

We propose techniques for the solution of the LP relaxation and the Lagrangean dual in combinatorial optimization and nonlinear programming problems. Our techniques find the optimal solution value and the optimal dual multipliers of the LP relaxation and the Lagrangean dual in polynomial time using as a subroutine either the Ellipsoid algorithm or the recent algorithm of Vaidya. Moreover, in problems of a certain structure our techniques find not only the optimal solution value, but the solution as well. Our techniques lead to significant improvements in the theoretical running time compared with previously known methods (interior point methods, Ellipsoid algorithm, Vaidya's algorithm). We use our method to the solution of the LP relaxation and the Langrangean dual of several classical combinatorial problems, like the traveling salesman problem, the vehicle routing problem, the Steiner tree problem, thek-connected problem, multicommodity flows, network design problems, network flow problems with side constraints, facility location problems,K-polymatroid intersection, multiple item capacitated lot sizing problem, and stochastic programming. In all these problems our techniques significantly improve the theoretical running time and yield the fastest way to solve them.     

The zero-one knapsack problem with equality constraint

The zero-one knapsack problem is a linear zero-one programming problem with a single inequality constraint. This problem has been extensively studied and many applications and efficient algorithms have been published. In this paper we consider a similar problem, one with an equality instead of the inequality constraint. By replacing the equality by two inequalities one of which is placed in the economic function, a Lagrangean relaxation of the problem is obtained. The relation between the relaxed problem and the original problem is examined and it is shown how the optimal value of the relaxed problem varies with increasing values of the Lagrangean multiplier. Using these results an algorithm for solving the problem is proposed.The paper concludes with a discussion of computational experience.     

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.     

Efficient cuts in Lagrangean ‘Relax-and-cut’ schemes

Lagrangean relaxation produces bounds on the optimal value of (mixed) integer programming problems. These bounds, together with integer feasible solution values, provide intervals bracketing the optimal value of the original problem. When the residual gap, i.e., the relative size of the interval, is too large for the approximations to be deemed satisfactory, it is desirable to ‘strengthen’ the Lagrangean bounds. One possible strengthening technique consists of identifying cuts which are violated by the current Lagrangean solution, and dualizing them. Unfortunately not every valid inequality that is currently violated will improve the Lagrangean relaxation bound when dualized. This paper investigates what makes a violated cut ‘efficient’ in improving bounds. It also provides examples of efficient cuts for several (mixed) integer programming problems.     

A repeated matching heuristic for the single-source capacitated facility location problem

Facility location models form an important class of integer programming problems, with application in many areas such as the distribution and transportation industries. An important class of solution methods for these problems are so-called Lagrangean heuristics which have been shown to produce high quality solutions and which are at the same time robust. The general facility location problem can be divided into a number of special problems depending on the properties assumed. In the capacitated location problem each facility has a specific capacity on the service it provides. We describe a new solution approach for the capacitated facility location problem when each customer is served by a single facility. The approach is based on a repeated matching algorithm which essentially solves a series of matching problems until certain convergence criteria are satisfied. The method generates feasible solutions in each iteration in contrast to Lagrangean heuristics where problem dependent heuristics must be used to construct a feasible solution. Numerical results show that the approach produces solutions which are of similar and often better than those produced using the best Lagrangean heuristics.     

Algorithms for a multi-level network optimization problem

In this paper we work on a multi-level network optimization problem that integrates into the same model important aspects of: (i) discrete facility location, (ii) topological network design, and (iii) network dimensioning. Potential applications for the model are discussed, stressing its growing importance. The multi-level network optimization problem treated is defined and a mathematical programming formulation is presented. We make use of a branch-and-bound algorithm based on Lagrangean relaxation lower bounds to introduce some new powerful auxiliary algorithms to exactly solve the problem. We conduct a set of computational experiments that indicate the quality of the proposed approach.     

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.     

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.     

Vector maximisation and lagrange multipliers

The Lagrangean function for scalar constrained optimisation problems is extended in a directly analogous manner to constrained vector optimisation problems. Some simple saddle point results are presented for vector maxima sets. Conditions are given for the characterisation of the vector maximum set of the original vector problem in terms of the vector maximum sets with respect to the vector Lagrangeans. Finally some attention is given to Lagrangean relaxation for vector optimisation problems as an extension of a result of Everett.