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.     

Lower bounds for nonlinear assignment problems using many body interactions

This paper concerns lower bounding techniques for the general α-adic assignment problem. The nonlinear objective function is linearized by the introduction of additional variables and constraints, thus yielding a mixed integer linear programming formulation of the problem. The concept of many body interactions is introduced to strengthen this formulation and incorporated in a modified formulation obtained by lifting the original representation to a higher dimensional space. This process involves two steps — (i) addition of new variables and constraints and (ii) incorporation of the new variables in the objective function. If this lifting process is repeated β times on an α-adic assignment problem along with the incorporation of higher order interactions, it results in the mixed-integer formulation of an equivalent (α + β)-adic assignment problem. The incorporation of many body interactions in the higher dimensional formulation improves its degeneracy properties and is also critical to the derivation of decomposition methods for the solution of these large scale mathematical programs in the higher dimensional space. It is shown that a lower bound to the optimal solution of the corresponding linear programming relaxation can be obtained by dualizing a subset of constraints in this formulation and solving O(N^2(α+β−1)) linear assignment problems, whose coefficients depend on the dual values. Moreover, it is proved that the optimal solution to the LP relaxation is obtained if we use the optimal duals for the solution of the linear assignment problems. This concept of many body interactions could be applied in designing algorithms for the solution of formulations obtained by lifting general MILP's. We illustrate all these concepts on the quadratic assignment problems With these decomposition bounds, we have found the provably optimal solutions of two unsolved QAP's of size 32 and have also improved upon existing lower bounds for other QAP's.     

Fleet assignment and routing with schedule synchronization constraints

This paper introduces a new type of constraints, related to schedule synchronization, in the problem formulation of aircraft fleet assignment and routing problems and it proposes an optimal solution approach. This approach is based on Dantzig–Wolfe decomposition/column generation. The resulting master problem consists of flight covering constraints, as in usual applications, and of schedule synchronization constraints. The corresponding subproblem is a shortest path problem with time windows and linear costs on the time variables and it is solved by an optimal dynamic programming algorithm. This column generation procedure is embedded into a branch and bound scheme to obtain integer solutions. A dedicated branching scheme was devised in this paper where the branching decisions are imposed on the time variables. Computational experiments were conducted using weekly fleet routing and scheduling problem data coming from an European airline. The test problems are solved to optimality. A detailed result analysis highlights the advantages of this approach: an extremely short subproblem solution time and, after several improvements, a very efficient master problem solution time.     

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.     

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.     

Nonsmooth exclusion test for finding all solutions of nonlinear equations

A new approach is proposed for finding all real solutions of systems of nonlinear equations with bound constraints. The zero finding problem is converted to a global optimization problem whose global minima with zero objective value, if any, correspond to all solutions of the original problem. A branch-and-bound algorithm is used with McCormick’s nonsmooth convex relaxations to generate lower bounds. An inclusion relation between the solution set of the relaxed problem and that of the original nonconvex problem is established which motivates a method to generate automatically, starting points for a local Newton-type method. A damped-Newton method with natural level functions employing the restrictive monotonicity test is employed to find solutions robustly and rapidly. Due to the special structure of the objective function, the solution of the convex lower bounding problem yields a nonsmooth root exclusion test which is found to perform better than earlier interval-analysis based exclusion tests. Both the componentwise Krawczyk operator and interval-Newton operator with Gauss-Seidel based root inclusion and exclusion tests are also embedded in the proposed algorithm to refine the variable bounds for efficient fathoming of the search space. The performance of the algorithm on a variety of test problems from the literature is presented, and for most of them, the first solution is found at the first iteration of the algorithm due to the good starting point generation.     

Cutting plane versus compact formulations for uncertain (integer) linear programs

Robustness is about reducing the feasible set of a given nominal optimization problem by cutting ??risky?? solutions away. To this end, the most popular approach in the literature is to extend the nominal model with a polynomial number of additional variables and constraints, so as to obtain its robust counterpart. Robustness can also be enforced by adding a possibly exponential family of cutting planes, which typically leads to an exponential formulation where cuts have to be generated at run time. Both approaches have pros and cons, and it is not clear which is the best one when approaching a specific problem. In this paper we computationally compare the two options on some prototype problems with different characteristics. We first address robust optimization à la Bertsimas and Sim for linear programs, and show through computational experiments that a considerable speedup (up to 2 orders of magnitude) can be achieved by exploiting a dynamic cut generation scheme. For integer linear problems, instead, the compact formulation exhibits a typically better performance. We then move to a probabilistic setting and introduce the uncertain set covering problem where each column has a certain probability of disappearing, and each row has to be covered with high probability. A related uncertain graph connectivity problem is also investigated, where edges have a certain probability of failure. For both problems, compact ILP models and cutting plane solution schemes are presented and compared through extensive computational tests. The outcome is that a compact ILP formulation (if available) can be preferable because it allows for a better use of the rich arsenal of preprocessing/cut generation tools available in modern ILP solvers. For the cases where such a compact ILP formulation is not available, as in the uncertain connectivity problem, we propose a restart solution strategy and computationally show its practical effectiveness.     

Optimality-based bound contraction with multiparametric disaggregation for the global optimization of mixed-integer bilinear problems

We address nonconvex mixed-integer bilinear problems where the main challenge is the computation of a tight upper bound for the objective function to be maximized. This can be obtained by using the recently developed concept of multiparametric disaggregation following the solution of a mixed-integer linear relaxation of the bilinear problem. Besides showing that it can provide tighter bounds than a commercial global optimization solver within a given computational time, we propose to also take advantage of the relaxed formulation for contracting the variables domain and further reduce the optimality gap. Through the solution of a real-life case study from a hydroelectric power system, we show that this can be an efficient approach depending on the problem size. The relaxed formulation from multiparametric formulation is provided for a generic numeric representation system featuring a base between 2 (binary) and 10 (decimal).     

Dual formulations and subgradient optimization strategies for linear programming relaxations of mixed-integer programs

This paper examines algorithmic strategies relating to the formulation of Lagrangian duals, and their solution via subgradient optimization, in the context of solving linear programming relaxations of mixed-integer programs. As in the current trend in integer programming, several researchers have found it beneficial to generate and add additional constraints to the model, prior to its solution, in order to tighten its linear programming relaxation. It becomes necessary, therefore, to be able to efficiently derive strong surrogate constraints and bounds based on such reformulations. This paper addresses the design and testing of the most viable technique available for exploiting such tight reformulations, namely, using Lagrangian relaxation in coordination with subgradient optimization. A computational study is conducted to test the efficiency of various Lagrangian dual formulations, and to investigate in the context of using subgradient optimization the effects of step size choices, problem scaling, conducting pattern moves, and projecting dual solutions onto subsets of violated dual constraints. Based on this study, certain recommendations are made regarding the manner in which one should implement such an approach.     

Enumeration Approach for Linear Complementarity Problems Based on a Reformulation-Linearization Technique

In this paper, we consider the linear complementarity problem (LCP) and present a global optimization algorithm based on an application of the reformulation-linearization technique (RLT). The matrix M associated with the LCP is not assumed to possess any special structure. In this approach, the LCP is formulated first as a mixed-integer 0–1 bilinear programming problem. The RLT scheme is then used to derive a new equivalent mixed-integer linear programming formulation of the LCP. An implicit enumeration scheme is developed that uses Lagrangian relaxation, strongest surrogate and strengthened cutting planes, and a heuristic, designed to exploit the strength of the resulting linearization. Computational experience on various test problems is presented.     

Method of reducing false-diffusion errors in convection—diffusion problems

False-diffusion errors in numerical solutions of convection-diffusion problems, in two- and three-dimensions, arise from the numerical approximations of the convection term in the conservation equations. For finite difference-based methods, one way to overcome these errors is to use an upwind approximation which essentially follows the streamlines. This approach, originally derived by Raithby is formally called the skew-upwind differencing scheme. Although this scheme shows promise and has proved to be more accurate than most others on a limited number of test problems, it does have some shortcomings. The method outlined in this paper retains the general objectives of the Raithby approach, but uses an entirely different formulation that eliminates the shortcomings of the original scheme. The paper describes the formulation of the proposed method, and demonstrates its performance on a standard test problem. A comparison with other schemes is also given. The results indicate that the new scheme has potential for minimizing false-diffusion in finite-difference based approaches for convection-diffusion problems.     

New and efficient algorithms for transfer prices and inventory holding policies in two-enterprise supply chains

We consider a multi-period problem of fair transfer prices and inventory holding policies in two enterprise supply chains. This problem was formulated as a mixed integer non-linear program by Gjerdrum et al. (Eur J Oper Res 143:582–599, 2002). Existing global optimization methods to solve this problem are computationally expensive. We propose a continuous approach based on difference of convex functions (DC) programming and DC Algorithms (DCA) for solving this combinatorial optimization problem. The problem is first reformulated as a DC program via an exact penalty technique. Afterward, DCA, an efficient local approach in non-convex programming framework, is investigated to solve the resulting problem. For globally solving this problem, we investigate a combined DCA-Branch and Bound algorithm. DCA is applied to get lower bounds while upper bounds are computed from a relaxation problem. The numerical results on several test problems show that the proposed algorithms are efficient: DCA provides a good integer solution in a short CPU time although it works on a continuous domain, and the combined DCA-Branch and Bound finds an \(\epsilon \) -optimal solution for large-scale problems in a reasonable time.     

An interval approach based on expectation optimization for fuzzy random bilevel linear programming problems

This paper considers a class of bilevel linear programming problems in which the coefficients of both objective functions are fuzzy random variables. The main idea of this paper is to introduce the Pareto optimal solution in a multi-objective bilevel programming problem as a solution for a fuzzy random bilevel programming problem. To this end, a stochastic interval bilevel linear programming problem is first introduced in terms of α-cuts of fuzzy random variables. On the basis of an order relation of interval numbers and the expectation optimization model, the stochastic interval bilevel linear programming problem can be transformed into a multi-objective bilevel programming problem which is solved by means of weighted linear combination technique. In order to compare different optimal solutions depending on different cuts, two criterions are given to provide the preferable optimal solutions for the upper and lower level decision makers respectively. Finally, a production planning problem is given to demonstrate the feasibility of the proposed approach.     

Advances in Interval Methods for Deterministic Global Optimization in Chemical Engineering

In recent years, it has been shown that strategies based on an interval-Newton approach can be used to reliably solve a variety of nonlinear equation solving and optimization problems in chemical process engineering, including problems in parameter estimation and in the computation of phase behavior. These strategies provide a mathematical and computational guarantee either that all solutions have been located in an equation solving problem or that the global optimum has been found in an optimization problem. The primary drawback to this approach is the potentially high computational cost. In this paper, we consider strategies for bounding the solution set of the linear interval equation system that must be solved in the context of the interval-Newton method. Recent preconditioning techniques for this purpose are reviewed, and a new bounding approach based on the use of linear programming (LP) techniques is presented. Using this approach it is possible to determine the desired bounds exactly (within round out), leading to significant overall improvements in computational efficiency. These techniques will be demonstrated using several global optimization problems, with focus on problems arising in chemical engineering, including parameter estimation and molecular modeling. These problems range in size from under ten variables to over two hundred, and are solved deterministically using the interval methodology.     

Scheduling projects to maximize net present value — the case of time-dependent,contingent cash flows

The problem of scheduling activities in a project to maximize its Net Present Value (NPV) has been solved for the case where net cash flow magnitudes are independent of the time of realization. This paper models a more realistic version of this problem — because of incentive payments and penalties for early and late event occurrences, respectively, and because of changing costs of resources over time, net cash flow magnitudes are dependent on the time of realization. We formulate an optimization program for this more general problem and present a simulated annealing solution approach. We test different implementation strategies for this algorithm and suggest a method for choosing neighborhood moves. We compare the NPVs of the solutions obtained from our formulation with the NPVs of early start schedules and with late start schedules for 168 different problems. These computational results show that the simulated annealing approach consistently produces substantially better solutions than the early start or late start schedules. Even poor simulated annealing neighborhood moves give improved solutions for most problems studied.     

Airport noise modelling and aircraft scheduling so as to minimize community annoyance

A mathematical model of the annoyance created at an airport by aircraft operations is developed. The model incorporates population distribution considerations around an airport and the annoyance caused by aircraft noise. The objective function of this model corresponds to seeking to minimize total population annoyance created by all aircraft operations in a 24-hour period. Several factors are included in this model as constraint relationships. Aircraft operations by type and time period are upper bounded. Demand for flight services is incorporated by including lower bounds on the number of operations by type of aircraft, runway used and time period. Also upper bounds on the number of operations for each runway are included. The mathematical model as formulated is recognized as corresponding to a nonlinear integer mathematical programming problem.The solution technique selected makes use of a successive linear approximation optimization algorithm. An especially attractive feature of this solution algorithm is that it is capable of obtaining solutions to large problems. For example, it would be feasible to attempt the solution of problems involving several thousand variables and over 500 linear constraints. This suggested solution algorithm was implemented on a computer and computational results obtained for example problems.     

D.C. programming approach for multicommodity network optimization problems with step increasing cost functions

We address a class of particularly hard-to-solve combinatorial optimization problems, namely that of multicommodity network optimization when the link cost functions are discontinuous step increasing. Unlike usual approaches consisting in the development of relaxations for such problems (in an equivalent form of a large scale mixed integer linear programming problem) in order to derive lower bounds, our d.c.(difference of convex functions) approach deals with the original continuous version and provides upper bounds. More precisely we approximate step increasing functions as closely as desired by differences of polyhedral convex functions and then apply DCA (difference of convex function algorithm) to the resulting approximate polyhedral d.c. programs. Preliminary computational experiments are presented on a series of test problems with structures similar to those encountered in telecommunication networks. They show that the d.c. approach and DCA provide feasible multicommodity flows x ^* such that the relative differences between upper bounds (computed by DCA) and simple lower bounds r:=(f(x^*)-LB)/{f(x^*)} lies in the range [4.2 %, 16.5 %] with an average of 11.5 %, where f is the cost function of the problem and LB is a lower bound obtained by solving the linearized program (that is built from the original problem by replacing step increasing cost functions with simple affine minorizations). It seems that for the first time so good upper bounds have been obtained.     

Bounds tightening based on optimality conditions for nonconvex box-constrained optimization

First-order optimality conditions have been extensively studied for the development of algorithms for identifying locally optimal solutions. In this work, we propose two novel methods that directly exploit these conditions to expedite the solution of box-constrained global optimization problems. These methods carry out domain reduction by application of bounds tightening methods on optimality conditions. This scheme is implicit and avoids explicit generation of optimality conditions through symbolic differentation, which can be memory and time intensive. The proposed bounds tightening methods are implemented in the global solver BARON. Computational results on a test library of 327 problems demonstrate the value of our proposed approach in reducing the computational time and number of nodes required to solve these problems to global optimality.     

Image space analysis of generalized fractional programs

The solution of a particular nonconvex program is usually very dependent on the structure of the problem. In this paper we identify classes of nonconvex problems involving either sums or products of ratios of linear terms which may be treated by analysis in a transformed space. In each class, the image space is defined by a mapping which associates a new variable with each original ratio of linear terms. In the image space, optimization is easy in certain directions, and the overall solution may be realized by sequentially optimizing in these directions.In addition to these ratio problems, we also show how to use image space analysis to treat the subclass of problems whose objective is to optimize a product of linear terms. For each class of nonconvex problems, we present an algorithm that locates global solutions by computing both upper and lower bounds on the solution and then solving a sequence of linear programming sub-problems. We also demonstrate the algorithms described in this paper by solving several example problems.     

Accelerating Branch-and-Bound through a Modeling Language Construct for Relaxation-Specific Constraints

In the tradition of modeling languages for optimization, a single model is passed to a solver for solution. In this paper, we extend BARON’s modeling language in order to facilitate the communication of problem-specific relaxation information from the modeler to the branch-and-bound solver. This effectively results into two models being passed from the modeling language to the solver. Three important application areas are identified and computational experiments are presented. In all cases, nonlinear constraints are provided only to the relaxation constructor in order to strengthen the lower bounding step of the algorithm without complicating the local search process. In the first application area, nonlinear constraints from the reformulation–linearization technique (RLT) are added to strengthen a problem formulation. This approach is illustrated for the pooling problem and computational results show that it results in a scheme that makes global optimization nearly as fast as local optimization for pooling problems from the literature. In the second application area, we communicate with the relaxation constructor the first-order optimality conditions for unconstrained global optimization problems. Computational experiments with polynomial programs demonstrate that this approach leads to a significant reduction of the size of the branch-and-bound search tree. In the third application, problem-specific nonlinear optimality conditions for the satisfiability problem are used to strengthen the lower bounding step and are found to significantly expedite the branch-and-bound algorithm when applied to a nonlinear formulation of this problem.