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.     

An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts

This paper presents a new exact algorithm for the Capacitated Vehicle Routing Problem (CVRP) based on the set partitioning formulation with additional cuts that correspond to capacity and clique inequalities. The exact algorithm uses a bounding procedure that finds a near optimal dual solution of the LP-relaxation of the resulting mathematical formulation by combining three dual ascent heuristics. The first dual heuristic is based on the q-route relaxation of the set partitioning formulation of the CVRP. The second one combines Lagrangean relaxation, pricing and cut generation. The third attempts to close the duality gap left by the first two procedures using a classical pricing and cut generation technique. The final dual solution is used to generate a reduced problem containing only the routes whose reduced costs are smaller than the gap between an upper bound and the lower bound achieved. The resulting problem is solved by an integer programming solver. Computational results over the main instances from the literature show the effectiveness of the proposed algorithm.      

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.     

A branch and bound algorithm for disassembly scheduling with assembly product structure

This paper considers a production planning problem in disassembly systems, which is the problem of determining the quantity and timing of disassembling end-of-use/life products in order to satisfy the demand of their parts or components over a planning horizon. The case of single product type without parts commonality is considered for the objective of minimizing the sum of setup and inventory holding costs. To show the complexity of the problem, we prove that the problem is NP-hard. Then, after deriving the properties of optimal solutions, a branch and bound algorithm is suggested that incorporates the Lagrangean relaxation-based upper and lower bounds. Computational experiments are performed on a number of randomly generated problems and the test results indicate that the branch and bound algorithm can give optimal solutions up to moderate-sized problems in a reasonable computation time. A Lagrangean heuristic for a viable alternative for large-sized problems is also suggested and compared with the existing heuristics to show its effectiveness.     

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.     

A heuristic lagrangean algorithm for the capacitated plant location problem

Lagrangean techniques have been widely applied to the uncapacitated plant location problem, and in some cases they have proven to be successfull even when capacitated problems with additional constraints are taken into account. In our paper we study the application of these techniques to the capacitated plant location problem when the model considered is a pure integer one. Several lagrangean decompositions are considered and for some of them heuristic algorithms have been designed to solve the resulting lagrangean subproblems, the heuristics consisting of a two phase procedure. The first (location phase) defines a set of multipliers from the analysis of the dual LP relaxation, and makes a choice of the plants considering the resulting subproblems as a particular case of the general assignment problems. Several heuristics have been studied for this second phase, based either on a decomposition of knapsack type subproblems through a definition of a set of penalties, or of looking into the duality gap and trying to reduce it. Computational experience is reported.     

Two-level evolutionary approach to the survivable mesh-based transport network topological design

The complete topology design problem of survivable mesh-based transport networks is to address simultaneously design of network topology, working path routing, and spare capacity allocation based on span-restoration. Each constituent problem in the complete design problem could be formulated as an Integer Programming (IP) and is proved to be NP\mathcal{NP} -hard. Due to a large amount of decision variables and constraints involved in the IP formulation, to solve the problem directly by exact algorithms (e.g. branch-and-bound) would be impractical if not impossible. In this paper, we present a two-level evolutionary approach to address the complete topology design problem. In the low-level, two parameterized greedy heuristics are developed to jointly construct feasible solutions (i.e., closed graph topologies satisfying all the mesh-based network survivable constraints) of the complete problem. Unlike existing “zoom-in”-based heuristics in which subsets of the constraints are considered, the proposed heuristics take all constraints into account. An estimation of distribution algorithm works on the top of the heuristics to tune the control parameters. As a result, optimal solution to the considered problem is more likely to be constructed from the heuristics with the optimal control parameters. The proposed algorithm is evaluated experimentally in comparison with the latest heuristics based on the IP software CPLEX, and the “zoom-in”-based approach on 28 test networks problems. The experimental results demonstrate that the proposed algorithm is more effective in finding high-quality topologies than the IP-based heuristic algorithm in 21 out of 28 test instances with much less computational costs, and performs significantly better than the “zoom-in”-based approach in 19 instances with the same computational costs.     

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.     

Base station location and channel allocation in a cellular network with emergency coverage requirements

The location of base stations (BS) and the allocation of channels are of paramount importance for the performance of cellular radio networks. Also cellular service providers are now being driven by the goal to enhance performance, particularly as it relates to the receipt and transmission of emergency crash notification messages generated by automobile telematics systems. In this paper, a Mixed Integer Programming (MIP) problem is proposed, which integrates into the same model the base station location problem, the frequency channel assignment problem and the emergency notification problem. The purpose of unifying these three problems in the same model is to treat the tradeoffs among them, providing a higher quality solution to the cellular system design. Some properties of the formulation are proposed that give us more insight into the problem structure. An instance generator is developed that randomly creates test problems. A few greedy heuristics are proposed to obtain quick solutions that turn out to be very good in some cases. To further improve the optimality gap, we develop a Lagrangean heuristic technique that builds on the solution obtained by the greedy heuristics. Finally, the performance of these methods is analyzed by extensive numerical tests and a sample case study is presented.     

Auxiliary tool allocation in flexible manufacturing systems

This paper analyses a new approach to the machine loading problem arising in flexible manufacturing systems (FMSs). This approach allows the operations to be assigned to machines assuming that machines have access to all the tools required for their operations. This exploits the flexibility of the FMS completely. Next an allocation of tools to machines is determined which satisfies the tool requirements for each machine and minimizes the total number of tools. Thus this approach minimizes the unnecessary tool duplications in the system and maximizes the tool utilization. The problem is modeled as an integer linear program (ILP). We notice that the main problem has a block diagonal structure which is decomposable by relaxing a set of linking constraints. Each separated sub-problem represents a problem of allocation of a single type of tools. We develop a branch-and-bound based exact solution procedure and three heuristic procedures to solve the sub-problems. Our lower bounding approach uses Lanrangean relaxation. The solutions to the Lagrangean relaxation are further used to determine the branching sequences and to develop heuristic approaches. Since finding even a feasible solution to the main problem is NP-hard, we develop only enumerative procedures to solve the main problem. Finally, these solution procedures are tested on randomly generated test problems.     

Lower and upper bounding procedures for the bin packing problem with concave loading cost

We address the one-dimensional bin packing problem with concave loading cost (BPPC), which commonly arises in less-than-truckload shipping services. Our contribution is twofold. First, we propose three lower bounds for this problem. The first one is the optimal solution of the continuous relaxation of the problem for which a closed form is proposed. The second one allows the splitting of items but not the fractioning of bins. The third one is based on a large-scale set partitioning formulation of the problem. In order to circumvent the challenges posed by the non-linearity of the objective function coefficients, we considered the inner-approximation of the concave load cost and derived a relaxed formulation that is solved by column generation. In addition, we propose two subset-sum-based heuristics. The first one is a constructive heuristic while the second one is a local search heuristic that iteratively attempts to improve the current solution by selecting pairs of bins and solving the corresponding subset sum-problem. We show that the worst-case performance of any BPPC heuristic and any concave loading cost function is bounded by 2. We present the results of an extensive computational study that was carried out on large set of benchmark instances. This study provides empirical evidence that the column generation-based lower bound and the local search heuristic consistently exhibit remarkable performance.     

Capacity and tool allocation problem in flexible manufacturing systems

This study addresses an allocation problem that arises in the semiconductor industry and flexible manufacturing systems where the tools should be loaded on computer numerical controlled (CNC) machines to process a number of operations. The time and tool magazine capacities of the CNC machines and the number of available tools of each type are limited. The objective is to maximize the total weight of operation assignments. We present a mixed integer programming formulation of the problem and show that the problem is NP-hard in the strong sense. We show that the linear programming relaxation upper bound dominates the best possible Lagrangean relaxation upper bound. We develop several lower bounding procedures and a lower bounding procedure using Lagrangean relaxation approach. Our computational results show that the upper and lower bounding procedures produce near-optimal solutions in reasonable times.     

The crane scheduling problem: models and solution approaches

In this paper, we study the crane scheduling problem for a vessel after the vessel is moored on a terminal and develop both exact and heuristic solution approaches for the problem. For small-sized instances, we develop a time-space network flow formulation with non-crossing constraints for the problem and apply an exact solution approach to obtain an optimal solution. For medium-sized instances, we develop a Lagrangian relaxation approach that allows us to obtain tight lower bounds and near-optimal solutions. For large-sized instances, we develop two heuristics and show that the error bounds of our heuristics are no more than 100%. Finally, we perform computational studies to show the effectiveness of our proposed solution approaches.     

具有机器适用限制的分布式置换流水车间问题的模型与算法

考虑具有机器适用限制的多个不同置换流水车间的调度问题. 机器适用限制指的是每个工件只能分配到其可加工工厂集合. 所有置换流水车间拥有的机器数相同但是具有不同的加工能力. 首先, 针对该问题建立了基于位置的混合整数线性规划模型; 进而, 对一般情况和三种特殊情况给出了具有较小近似比的多项式时间算法. 其次, 基于NEH方法提出了启发式算法NEHg, 并给出了以NEHg为上界的分支定界算法. 最后, 通过例子说明了NEHg启发式算法和分支定界算法的计算过程, 并进行大量的实验将NEHg与NEH算法结果进行比较, 从而验证了NEHg算法的有效性.     

A Lagrangian-based heuristic for the capacitated lot-sizing problem in parallel machines

This paper addresses the capacitated lot-sizing problem involving the production of multiple items on unrelated parallel machines. A production plan should be determined in order to meet the forecast demand for the items, without exceeding the capacity of the machines and minimize the sum of production, setup and inventory costs. A heuristic based on the Lagrangian relaxation of the capacity constraints and subgradient optimization is proposed. Initially, the heuristic is tested on instances of the single machine problem and results are compared with heuristics from the literature. For parallel machines and small problems the heuristic performance is tested against optimal solutions, and for larger problems it is compared with the lower bound provided by the Lagrangian relaxation.     

A fast heuristic method for minimizing traffic congestion on reconfigurable ring topologies

We describe the development of fast heuristics and methodologies for congestion minimization problems in directional wireless networks, and we compare their performance with optimal solutions. The focus is on the network layer topology control problem (NLTCP) defined by selecting an optimal ring topology as well as the flows on it. Solutions to NLTCP need to be computed in near realtime due to changing weather and other transient conditions and which generally preclude traditional optimization strategies. Using a mixed-integer linear programming formulation, we present both new constraints for this problem and fast heuristics to solve it. The new constraints are used to increase the lower bound from the linear programming relaxation and hence speed up the solution of the optimization problem by branch and bound. The upper and lower bounds for the optimal objective function to the mixed integer problem then serve to evaluate new node-swapping heuristics which we also present. Through a series of tests on different sized networks with different traffic demands, we show that our new heuristics achieve within about 0.5% of the optimal value within seconds.     

Exact and heuristic methods for placing ships in locks

The ship placement problem constitutes a daily challenge for planners in tide river harbours. In essence, it entails positioning a set of ships into as few lock chambers as possible while satisfying a number of general and specific placement constraints. These constraints make the ship placement problem different from traditional 2D bin packing. A mathematical formulation for the problem is presented. In addition, a decomposition model is developed which allows for computing optimal solutions in a reasonable time. A multi-order best fit heuristic for the ship placement problem is introduced, and its performance is compared with that of the left-right-left-back heuristic. Experiments on simulated and real-life instances show that the multi-order best fit heuristic beats the other heuristics by a landslide, while maintaining comparable calculation times. Finally, the new heuristic’s optimality gap is small, while it clearly outperforms the exact approach with respect to calculation time.     

A multi-space sampling heuristic for the vehicle routing problem with stochastic demands

The vehicle routing problem with stochastic demands consists in designing transportation routes of minimal expected cost to satisfy a set of customers with random demands of known probability distributions. This paper proposes a simple yet effective heuristic approach that uses randomized heuristics for the traveling salesman problem, a tour partitioning procedure, and a set partitioning formulation to sample the solution space and find high-quality solutions for the problem. Computational experiments on benchmark instances from the literature show that the proposed approach is competitive with the state-of-the-art algorithm for the problem in terms of both accuracy and efficiency. In experiments conducted on a set of 40 instances, the proposed approach unveiled four new best-known solutions (BKSs) and matched another 24. For the remaining 12 instances, the heuristic reported average gaps with respect to the BKS ranging from 0.69 to 0.15 % depending on its configuration.     

Lagrangean heuristic for primary routes assignment in survivable connection-oriented networks

Our discussion in this article centers on the application of a Lagrangean relaxation and a subgradient optimization technique to the problem of primary route assignment (PRA) in survivable connection-oriented networks. The PRA problem consists in a static optimization of primary routes minimizing the Lost Flow in Node (LFN) function. The major contribution of this work is a combination of the Lagrangean relaxation with other heuristic algorithms. We evaluate the performance of the proposed Lagrangean-based heuristic by making a comparison with their counterparts including evolutionary algorithm and GRASP using various network topologies and demand patterns. The results of simulation tests show that the new algorithm provides sub-optimal results, which are better than other heuristics.     

Optimizing a dynamic order-picking process

This research studies the problem of batching orders in a dynamic, finite-horizon environment to minimize order tardiness and overtime costs of the pickers. The problem introduces the following trade-off: at every period, the picker has to decide whether to go on a tour and pick the accumulated orders, or to wait for more orders to arrive. By waiting, the picker risks higher tardiness of existing orders on the account of lower tardiness of future orders. We use a Markov decision process (MDP) based approach to set an optimal decision making policy. In order to evaluate the potential improvement of the proposed approach in practice, we compare the optimal policy with two naïve heuristics: (1) “Go on tour immediately after an order arrives”, and, (2) “Wait as long as the current orders can be picked and supplied on time”. The optimal policy shows a considerable improvement over the naïve heuristics, in the range of 7–99%, where the specific values depend on the picking process parameters. We have found that one measure, the slack percentage of the picking process, associated with the difference between the promised lead time and the single item picking time, predicts quite accurately the cost reduction generated by the optimal policy. Since relatively small-scale problems could be solved by the optimal algorithm, a heuristic was developed, based on the structure and properties of the optimal solutions. Numerical results show that the proposed heuristic, MDP-H, outperforms the naïve heuristics in all experiments. As compared to the optimal solution, MDP-H provides close to optimal results for a slack of up to 40%.