A Lagrangian relaxation approach for network inventory control of stochastic revenue management with perishable commodities

Airline seat inventory control is the allocation of seats in the same cabin to different fare classes such that the total revenue is maximized. Seat allocation can be modelled as dynamic stochastic programs, which are computationally intractable in network settings. Deterministic and probabilistic mathematical programming models are therefore used to approximate dynamic stochastic programs. The probabilistic model, which is the focus of this paper, has a nonlinear objective function, which makes the solution of large-scale practical instances with off-the-shelf solvers prohibitively time consuming. In this paper, we propose a Lagrangian relaxation (LR) method for solving the probabilistic model by exploring the fact that LR problems are decomposable. We show that the solutions of the LR problems admit a simple analytical expression which can be resolved directly. Both the booking limit policy and the bid-price policy can be implemented using this method. Numerical simulations demonstrate the effectiveness of the proposed method.     

A Lagrangian relaxation approach to the edge-weighted clique problem

The b-clique polytope CPⁿ_b is the convex hull of the node and edge incidence vectors of all subcliques of size at most b of a complete graph on n nodes. Including the Boolean quadric polytope QPⁿ=CPⁿ_n as a special case and being closely related to the quadratic knapsack polytope, it has received considerable attention in the literature. In particular, the max-cut problem is equivalent with optimizing a linear function over CPⁿ_n. The problem of optimizing linear functions over CPⁿ_b has so far been approached via heuristic combinatorial algorithms and cutting-plane methods.We study the structure of CPⁿ_b in further detail and present a new computational approach to the linear optimization problem based on the idea of integrating cutting planes into a Lagrangian relaxation of an integer programming problem that Balas and Christofides had suggested for the traveling salesman problem. In particular, we show that the separation problem for tree inequalities becomes polynomial in our Lagrangian framework. Finally, computational results are presented.     

A Lagrangian relaxation approach to large-scale flow interception problems

The paper presents a tight Lagrangian bound and an efficient dual heuristic for the flow interception problem. The proposed Lagrangian relaxation decomposes the problem into two subproblems that are easy to solve. Information from one of the subproblems is used within a dual heuristic to construct feasible solutions and is used to generate valid cuts that strengthen the relaxation. Both the heuristic and the relaxation are integrated into a cutting plane method where the Lagrangian bound is calculated using a subgradient algorithm. In the course of the algorithm, a valid cut is added and integrated efficiently in the second subproblem and is updated whenever the heuristic solution improves. The algorithm is tested on randomly generated test problems with up to 500 vertices, 12,483 paths, and 43 facilities. The algorithm finds a proven optimal solution in more than 75% of the cases, while the feasible solution is on average within 0.06% from the upper bound.     

A Lagrangian relaxation approach to multi-period inventory/distribution planning

We consider a multi-period inventory/distribution planning problem (MPIDP) in a one-warehouse multiretailer distribution system where a fleet of heterogeneous vehicles delivers products from a warehouse to several retailers. The objective of the MPIDP is to minimise transportation costs for product delivery and inventory holding costs at retailers over the planning horizon. In this research, the problem is formulated as a mixed integer linear programme and solved by a Lagrangian relaxation approach. A subgradient optimisation method is employed to obtain lower bounds. We develop a Lagrangian heuristic algorithm to find a good feasible solution of the MPIDP. Computational experiments on randomly generated test problems showed that the suggested algorithm gave relatively good solutions in a reasonable amount of computation time.     

A novel Lagrangian relaxation approach for a hybrid flowshop scheduling problem in the steelmaking-continuous casting process

One of the largest bottlenecks in iron and steel production is the steelmaking-continuous casting (SCC) process, which consists of steel-making, refining and continuous casting. The SCC scheduling is a complex hybrid flowshop (HFS) scheduling problem with the following features: job grouping and precedence constraints, no idle time within the same group of jobs and setup time constraints on the casters. This paper first models the scheduling problem as a mixed-integer programming (MIP) problem with the objective of minimizing the total weighted earliness/tardiness penalties and job waiting. Next, a Lagrangian relaxation (LR) approach relaxing the machine capacity constraints is presented to solve the MIP problem, which decomposes the relaxed problem into two tractable subproblems by separating the continuous variables from the integer ones. Additionally, two methods, i.e., the boundedness detection method and time horizon method, are explored to handle the unboundedness of the decomposed subproblems in iterations. Furthermore, an improved subgradient level algorithm with global convergence is developed to solve the Lagrangian dual (LD) problem. The computational results and comparisons demonstrate that the proposed LR approach outperforms the conventional LR approaches in terms of solution quality, with a significantly shorter running time being observed.     

A surrogate and Lagrangian approach to constrained network problems

This paper presents the use of surrogate constraints and Lagrange multipliers to generate advanced starting solutions to constrained network problems. The surrogate constraint approach is used to generate a singly constrained network problem which is solved using the algorithm of Glover, Karney, Klingman and Russell [13]. In addition, we test the use of the Lagrangian function to generate advanced starting solutions. In the Lagrangian approach, the subproblems are capacitated network problems which can be solved using very efficient algorithms.The surrogate constraint approach is implemented using the multiplier update procedure of Held, Wolfe and Crowder [16]. The procedure is modified to include a search in a single direction to prevent periodic regression of the solution. We also introduce a reoptimization procedure which allows the solution from thekth subproblem to be used as the starting point for the next surrogate problem for which it is infeasible once the new surrogate constraint is adjoined.The algorithms are tested under a variety of conditions including: large-scale problems, number and structure of the non-network constraints, and the density of the non-network constraint coefficients.The testing clearly demonstrates that both the surrogate constraint and Langrange multipliers generate advanced starting solutions which greatly improve the computational effort required to generate an optimal solution to the constrained network problem. The testing demonstrates that the extra effort required to solve the singly constrained network subproblems of the surrogate constraints approach yields an improved advanced starting point as compared to the Lagrangian approach. It is further demonstrated that both of the relaxation approaches are much more computationally efficient than solving the problem from the beginning with a linear programming algorithm.     

An alternative framework to Lagrangian relaxation approach for job shop scheduling

A new Lagrangian relaxation (LR) approach is developed for job shop scheduling problems. In the approach, operation precedence constraints rather than machine capacity constraints are relaxed. The relaxed problem is decomposed into single or parallel machine scheduling subproblems. These subproblems, which are NP-complete in general, are approximately solved by using fast heuristic algorithms. The dual problem is solved by using a recently developed “surrogate subgradient method” that allows approximate optimization of the subproblems. Since the algorithms for subproblems do not depend on the time horizon of the scheduling problems and are very fast, our new LR approach is efficient, particularly for large problems with long time horizons. For these problems, the machine decomposition-based LR approach requires much less memory and computation time as compared to a part decomposition-based approach as demonstrated by numerical testing.     

A Lagrangian relaxation approach to solve the second phase of the exam scheduling problem

The problem of scheduling final exams at a large university can be viewed as a three phase process. The first phase consists of grouping the exams into sets called exam blocks. The second phase deals with the assignment of exam blocks to exam days and the third phase consists of arranging the exam days and also arranging the blocks within days.In this paper, we present new integer programming formulations for the second phase of the scheduling problem. We present an integer program with a single objective of minimizing the number of students with two or more exams per day. We then present a Lagrangian relaxation based solution procedure to solve this problem. Further, we present a bicriterion integer programming formulation to minimize the number of students with two exams per day and the number of students with three exams per day. Finally, we present some computational experience using randomly generated problems as well as real world data obtained from the State University of New York at Buffalo.     

A Lagrangian relaxation approach to simultaneous strategic and tactical planning in supply chain design

We study a multi-echelon joint inventory-location model that simultaneously determines the location of warehouses and inventory policies at the warehouses and retailers. The model is formulated as a nonlinear mixed-integer program, and is solved using a Lagrangian relaxation-based approach. The efficiency of the algorithm and benefits of integration are evaluated through a computational study.     

Partial Lagrangian relaxation for general quadratic programming

We give a complete characterization of constant quadratic functions over an affine variety. This result is used to convexify the objective function of a general quadratic programming problem (Pb) which contains linear equality constraints. Thanks to this convexification, we show that one can express as a semidefinite program the dual of the partial Lagrangian relaxation of (Pb) where the linear constraints are not relaxed. We apply these results by comparing two semidefinite relaxations made from two sets of null quadratic functions over an affine variety.      

A Lagrangian relaxation approach to the mixed-product assembly line sequencing problem: A case study of a door-lock company in Taiwan

In mixed-product assembly line sequencing, the production resources required for the assembly lines should be scheduled to minimize the overall cost and meet customer demand. In this paper, we study an assembly line sequencing problem for the door-lock industry in Taiwan and develop an integer programming formulation with realistic constraints. The complex solution space makes the resulting program difficult to solve using commercial optimization packages. Therefore, a heuristic based on the Lagrangian relaxation principle is developed to solve this problem efficiently. We evaluate the efficiency of the developed Lagrangian relaxation heuristic by comparing its solutions with those obtained using a commercial optimization package: the computational results show that the developed heuristic solves the real-world problem faster than the optimization package by almost 15 times in CPU time at a comparable solution quality.     

An improved Lagrangian relaxation and dual ascent approach to facility location problems

The literature knows semi-Lagrangian relaxation as a particular way of applying Lagrangian relaxation to certain linear mixed integer programs such that no duality gap results. The resulting Lagrangian subproblem usually can substantially be reduced in size. The method may thus be more efficient in finding an optimal solution to a mixed integer program than a “solver” applied to the initial MIP formulation, provided that “small” optimal multiplier values can be found in a few iterations. Recently, a simplification of the semi-Lagrangian relaxation scheme has been suggested in the literature. This “simplified” approach is actually to apply ordinary Lagrangian relaxation to a reformulated problem and still does not show a duality gap, but the Lagrangian dual reduces to a one-dimensional optimization problem. The expense of this simplification is, however, that the Lagrangian subproblem usually can not be reduced to the same extent as in the case of ordinary semi-Lagrangian relaxation. Hence, an effective method for optimizing the Lagrangian dual function is of utmost importance for obtaining a computational advantage from the simplified Lagrangian dual function. In this paper, we suggest a new dual ascent method for optimizing both the semi-Lagrangian dual function as well as its simplified form for the case of a generic discrete facility location problem and apply the method to the uncapacitated facility location problem. Our computational results show that the method generally only requires a very few iterations for computing optimal multipliers. Moreover, we give an interesting economic interpretation of the semi-Lagrangian multiplier(s).     

A matheuristic based on Lagrangian relaxation for the multi-activity shift scheduling problem

The multi-activity shift scheduling problem involves assigning a sequence of activities to a set of employees. In this paper, we consider the variant where the employees have different qualifications and each activity must be performed in a specified time window; i.e., we specify the earliest start period and the latest finish period. We propose a matheuristic in which Lagrangian relaxation is used to identify a subset of promising shifts, and a restricted set covering problem is solved to find a feasible solution. Each shift is represented by a context-free grammar. Computational tests are carried out on two sets of instances from the literature. For the first set, the matheuristic finds a solution with an optimality gap less than 0.01% for 70% of the instances and improves the best-known solution for 16% of them; for the second set, the matheuristic reaches the best-known solutions for 55% of the instances and finds better solutions for 37.5% of them.     

Partial Lagrangian relaxation for the unbalanced orthogonal Procrustes problem

Based on a novel reformulation of the feasible region, we propose and analyze a partial Lagrangian relaxation approach for the unbalanced orthogonal Procrustes problem (UOP). With a properly selected Lagrangian multiplier, the Lagrangian relaxation (LR) is equivalent to the recent matrix lifting semidefinite programming relaxation (MSDR), which has much more variables and constraints. Numerical results show that (LR) is solved more efficiently than (MSDR). Moreover, based on the special structure of (LR), we successfully employ the well-known Frank–Wolfe algorithm to efficiently solve very large instances of (LR). The rate of the convergence is shown to be independent of the row-dimension of the matrix variable of (UOP). Finally, motivated by (LR), we propose a Lagrangian heuristic for (UOP). Numerical results show that it can efficiently find the global optimal solutions of some randomly generated instances of (UOP).     

Lagrangian relaxation based algorithm for trigeneration planning with storages

Trigeneration is a booming power production technology where three energy commodities are simultaneously produced in a single integrated process. Electric power, heat (e.g. hot water) and cooling (e.g. chilled water) are three typical energy commodities in the trigeneration system. The production of three energy commodities follows a joint characteristic. This paper presents a Lagrangian relaxation (LR) based algorithm for trigeneration planning with storages based on deflected subgradient optimization method. The trigeneration planning problem is modeled as a linear programming (LP) problem. The linear cost function poses the convergence challenge to the LR algorithm and the joint characteristic of trigeneration plants makes the operating region of trigeneration system more complicated than that of power-only generation system and that of combined heat and power (CHP) system. We develop an effective method for the long-term planning problem based on the proper strategy to form Lagrangian subproblems and solve the Lagrangian dual (LD) problem based on deflected subgradient optimization method. We also develop a heuristic for restoring feasibility from the LD solution. Numerical results based on realistic production models show that the algorithm is efficient and near-optimal solutions are obtained.     

A Lagrangian approach to intrinsic linearized elasticity

We consider the pure traction problem and the pure displacement problem of three-dimensional linearized elasticity. We show that, in each case, the intrinsic approach leads to a quadratic minimization problem constrained by Donati-like relations. Using the Babu?ka–Brezzi inf–sup condition, we then show that, in each case, the minimizer of the constrained minimization problem found in an intrinsic approach is the first argument of the saddle-point of an ad hoc Lagrangian, so that the second argument of this saddle-point is the Lagrange multiplier associated with the corresponding constraints.     

Shape Hessian for generalized Oseen flow by differentiability of a minimax: A Lagrangian approach

The goal of this paper is to compute the shape Hessian for a generalized Oseen problem with nonhomogeneous Dirichlet boundary condition by the velocity method. The incompressibility will be treated by penalty approach. The structure of the shape gradient and shape Hessian with respect to the shape of the variable domain for a given cost functional are established by an application of the Lagrangian method with function space embedding technique. This work was supported by the National Natural Science Fund of China (No. 10371096) for ZM Gao and YC Ma.