A Lagrangian decomposition approach for the pump scheduling problem in water networks

Dynamic pricing has become a common form of electricity tariff, where the price of electricity varies in real time based on the realized electricity supply and demand. Hence, optimizing industrial operations to benefit from periods with low electricity prices is vital to maximizing the benefits of dynamic pricing. In the case of water networks, energy consumed by pumping is a substantial cost for water utilities, and optimizing pump schedules to accommodate for the changing price of energy while ensuring a continuous supply of water is essential. In this paper, a Mixed-Integer Non-linear Programming (MINLP) formulation of the optimal pump scheduling problem is presented. Due to the non-linearities, the typical size of water networks, and the discretization of the planning horizon, the problem is not solvable within reasonable time using standard optimization software. We present a Lagrangian decomposition approach that exploits the structure of the problem leading to smaller problems that are solved independently. The Lagrangian decomposition is coupled with a simulation-based, improved limited discrepancy search algorithm that is capable of finding high quality feasible solutions. The proposed approach finds solutions with guaranteed upper and lower bounds. These solutions are compared to those found by a mixed-integer linear programming approach, which uses a piecewise-linearization of the non-linear constraints to find a global optimal solution of the relaxation. Numerical testing is conducted on two real water networks and the results illustrate the significant costs savings due to optimizing pump schedules.     

A nonlinear Lagrangian dual for integer programming

Nonlinear Lagrangian theory offers a success guarantee for the dual search via construction of a nonlinear support of the perturbation function at the optimal point. In this paper, a new nonlinear dual formulation of an exponential form is proposed for bounded integer programming. This new formulation possesses an asymptotic strong duality property and guarantees a success in identifying a primal optimum solution. No actual dual search is needed in the solution process when the parameter of the nonlinear Lagrangian formulation is set to be large enough.     

Success Guarantee of Dual Search in Integer Programming: p-th Power Lagrangian Method

Although the Lagrangian method is a powerful dual search approach in integer programming, it often fails to identify an optimal solution of the primal problem. The p-th power Lagrangian method developed in this paper offers a success guarantee for the dual search in generating an optimal solution of the primal integer programming problem in an equivalent setting via two key transformations. One other prominent feature of the p-th power Lagrangian method is that the dual search only involves a one-dimensional search within [0,1]. Some potential applications of the method as well as the issue of its implementation are discussed.     

Comment on “A nonlinear Lagrangian dual for integer programming”

We present a counterexample and correction to the contention by Xu and Li that the nonlinear Lagrangian dual problem they propose [Oper. Res. Lett. 30 (2002) 401] asymptotically has no duality gap.     

Finding improving directions in Lagrangian relaxation by fictitious play: A NASA scheduling application

An improving direction for Lagrangian dual prices can be found by solving (or solving approximately) a two person zero-sum game. While this method is impractical in many situations, its practical use is illustrated in a scheduling application. In this implementation, the game is solved approximately by fictitious play.     

Optimization-based heuristics for underground mine scheduling

Underground mine production scheduling possesses mathematical structure similar to and yields many of the same challenges as general scheduling problems. That is, binary variables represent the time at which various activities are scheduled. Typical objectives seek to minimize costs or some measure of production time, or to maximize net present value; two principal types of constraints exist: (i) resource constraints and (ii) precedence constraints. In our setting, we maximize “discounted metal production” for the remaining life of an underground lead and zinc mine that uses three different underground methods to extract the ore. Resource constraints limit the grade, tonnage, and backfill paste (used for structural stability) in each time period, while precedence constraints enforce the sequence in which extraction (and backfill) is performed in accordance with the underground mining methods used. We tailor exact and heuristic approaches to reduce model size, and develop an optimization-based decomposition heuristic; both of these methods transform a computationally intractable problem to one for which we obtain solutions in seconds, or, at most, hours for problem instances based on data sets from the Lisheen mine near Thurles, Ireland.     

An algebraic geometry algorithm for scheduling in presence of setups and correlated demands

We study here a problem of schedulingn job types onm parallel machines, when setups are required and the demands for the products are correlated random variables. We model this problem as a chance constrained integer program.Methods of solution currently available—in integer programming and stochastic programming—are not sufficient to solve this model exactly. We develop and introduce here a new approach, based on a geometric interpretation of some recent results in Gröbner basis theory, to provide a solution method applicable to a general class of chance constrained integer programming problems.Out algorithm is conceptually simple and easy to implement. Starting from a (possibly) infeasible solution, we move from one lattice point to another in a monotone manner regularly querying a membership oracle for feasibility until the optimal solution is found. We illustrate this methodology by solving a problem based on a real system.Corresponding author.     

MIP-based decomposition strategies for large-scale scheduling problems in multiproduct multistage batch plants: A benchmark scheduling problem of the pharmaceutical industry

An efficient systematic iterative solution strategy for solving real-world scheduling problems in multiproduct multistage batch plants is presented. Since the proposed method has its core a mathematical model, two alternative MIP scheduling formulations are suggested. The MIP-based solution strategy consists of a constructive step, wherein a feasible and initial solution is rapidly generated by following an iterative insertion procedure, and an improvement step, wherein the initial solution is systematically enhanced by implementing iteratively several rescheduling techniques, based on the mathematical model. A salient feature of our approach is that the scheduler can maintain the number of decisions at a reasonable level thus reducing appropriately the search space. A fact that usually results in manageable model sizes that often guarantees a more stable and predictable optimization model behavior. The proposed strategy performance is tested on several complicated problem instances of a multiproduct multistage pharmaceuticals scheduling problem. On average, high quality solutions are reported with relatively low computational effort. Authors encourage other researchers to adopt the large-scale pharmaceutical scheduling problem to test on it their solution techniques, and use it as a challenging comparison reference.     

Computing redundant resources for the resource constrained project scheduling problem

Several efficient lower bounds and time-bound adjustment methods for the resource constrained project scheduling problem (RCPSP) have recently been proposed. Some of them are based on redundant resources. In this paper we define redundant functions which are very useful for computing redundant resources. We also describe an algorithm for computing all maximal redundant functions. Once all these redundant functions have been determined, we have to identify those that are useful for bounding. Surprisingly, their number is reasonable even for large resource capacities, so a representative subset of them can be tabulated to be used efficiently. Computational results on classical RCPSP instances confirm their usefulness.     

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.     

Elastic Constraint Branching, the Wedelin/Carmen Lagrangian Heuristic and Integer Programming for Personnel Scheduling

The Wedelin algorithm is a Lagrangian based heuristic that is being successfully used by Carmen Systems to solve large crew pairing problems within the airline industry. We extend the Wedelin approach by developing an implementation for personnel scheduling problems (also termed staff rostering problems) that exploits the special structure of these problems. We also introduce elastic constraint branching with the twin aims of improving the performance of our new approach and making it more column generation friendly. Numerical results show that our approach can outperform the commercial solver CPLEX on difficult commercial rostering problems.     

A dual strategy for solving the linear programming relaxation of a driver scheduling system

A Mathematical Programming model of a driver scheduling system is described. This consists of set covering and partitioning constraints, possibly user-supplied side constraints, and two pre-emptively ordered objectives. The previous solution strategy addressed the two objectives using separate Primal Simplex optimisations; a new strategy uses a single weighted objective function and a Dual Simplex algorithm initiated by a specially developed heuristic. Computational results are reported.     

A new augmented Lagrangian function for inequality constraints in nonlinear programming problems

In this paper, a new augmented Lagrangian function is introduced for solving nonlinear programming problems with inequality constraints. The relevant feature of the proposed approach is that, under suitable assumptions, it enables one to obtain the solution of the constrained problem by a single unconstrained minimization of a continuously differentiable function, so that standard unconstrained minimization techniques can be employed. Numerical examples are reported.     

对等式约束非线性规划问题的Hestenes-Powell增广拉格朗日函数的进一步研究

本文对用无约束极小化方法求解等式约束非线性规划问题的Hestenes-Powell 增广拉格朗日函数作了进一步研究．在适当的条件下,我们建立了Hestenes-Powell增广拉格朗日函数在原问题变量空间上的无约束极小与原约束问题的解之间的关系,并且也给出了Hestenes-Powell增广拉格朗日函数在原问题变量和乘子变量的积空间上的无约束极小与原约束问题的解之间的一个关系．因此,从理论的观点来看,原约束问题的解和对应的拉格朗日乘子值不仅可以用众所周知的乘子法求得,而且可以通过对Hestenes-Powell 增广拉格朗日函数在原问题变量和乘子变量的积空间上执行一个单一的无约束极小化来获得．     

Stochastic recursive inclusion in two timescales with an application to the Lagrangian dual problem

In this paper we present a framework to analyze the asymptotic behavior of two timescale stochastic approximation algorithms including those with set-valued mean fields. This paper builds on the works of Borkar and Perkins & Leslie. The framework presented herein is more general as compared to the synchronous two timescale framework of Perkins & Leslie, however the assumptions involved are easily verifiable. As an application, we use this framework to analyze the two timescale stochastic approximation algorithm corresponding to the Lagrangian dual problem in optimization theory.     

Discrete and continuous time representations and mathematical models for large production scheduling problems: A case study from the pharmaceutical industry

The underlying time framework used is one of the major differences in the basic structure of mathematical programming formulations used for production scheduling problems. The models are either based on continuous or discrete time representations. In the literature there is no general agreement on which is better or more suitable for different types of production or business environments. In this paper we study a large real-world scheduling problem from a pharmaceutical company. The problem is at least NP-hard and cannot be solved with standard solution methods. We therefore decompose the problem into two parts and compare discrete and continuous time representations for solving the individual parts. Our results show pros and cons of each model. The continuous formulation can be used to solve larger test cases and it is also more accurate for the problem under consideration.     

The implementor/adversary algorithm for the cyclic and robust scheduling problem in health-care

A general problem in health-care consists in allocating some scarce medical resource, such as operating rooms or medical staff, to medical specialties in order to keep the queue of patients as short as possible. A major difficulty stems from the fact that such an allocation must be established several months in advance, and the exact number of patients for each specialty is an uncertain parameter. Another problem arises for cyclic schedules, where the allocation is defined over a short period, e.g. a week, and then repeated during the time horizon. However, the demand typically varies from week to week: even if we know in advance the exact demand for each week, the weekly schedule cannot be adapted accordingly. We model both the uncertain and the cyclic allocation problem as adjustable robust scheduling problems. We develop a row and column generation algorithm to solve this problem and show that it corresponds to the implementor/adversary algorithm for robust optimization recently introduced by Bienstock for portfolio selection. We apply our general model to compute master surgery schedules for a real-life instance from a large hospital in Oslo.     

A representation model for the solving-time distribution of a set of design tasks in new product development (NPD)

Given the potential risks of new product development projects (NPD), the characteristics of the design tasks solving-time distributions are critical for their effective management. In OR we need to find what operational characteristics of design tasks may delay projects. Other researchers already identified the technological novelty, the magnitude of the design tasks, the interactions between design tasks in an NPD project, and the balancing between projects among the most important causes of the unpredictability of the design tasks lead times in NPD projects.