Optimal solution of cellular manufacturing system design: Benders' decomposition approach

In this paper, a mathematical model for cellular manufacturing system (CMS) design which incorporates three critical aspects - resource utilization, alternate routings, and practical constraints, is presented. The model is shown to be NP-complete. A linear, mixed-integer version of the model which not only has fewer integer variables compared to most other models in the literature, but one that also permits us to solve it optimally using Benders' decomposition approach is presented. Some results that allow us to solve the problem efficiently as well as computational results with Benders' decomposition algorithm and a modified version are presented.     

Multicommodity Flow Problem with Variable Arcs Capacities

The problem of maximizing the sum of the flows of all commodities in a network where the capacities of some arcs can be increased by integer numbers within a fixed budget is solved in this paper. Benders' technique is used to decompose the problem. Then Rosen's primal partitioning and non-linear duality theory are used to solve the subproblems generated by the Benders' decomposition. An application of a multicommodity network to the defence problem is mentioned.     

Solving the Segregated Storage Problem with Benders' Partitioning

We investigate the application of Benders' partitioning to a mixed integer programming formulation of the segregated storage problem. The dual subproblem reduces to an efficiently-solvable network flow problem. This approach is compared empirically to Neebe's multiplier adjustment procedure. Benders' procedure is shown to be computationally effective for an important class of practical applications having high demand-to-capacity ratios and fewer products than compartments.     

Characterization of local solutions for a class of nonconvex programs

A nonconvex programming problem, which arises in the context of application of Benders' decomposition procedure to a class of network optimization problems, is considered. Conditions which are both necessary and sufficient for a local maximum are derived. The concept of a basic local maximum is introduced, and it is shown that there is a finite number of basic local maxima and at least one such local maximum is optimal.     

A Profit-maximizing Plant-loading Model with Demand Fill-rate Constraints

This paper discusses a new formulation of a class of plant product-mix loading problems which are characterized by capacitated production facilities, demand fill-rate requirements, fixed facility costs, concave variable production costs and an integrated network structure which encompasses inbound supply and outbound distribution flows. In particular, we are interested in assigning product lines and volumes to a set of capacitated plants under the demand fill-rate constraints. Fixed costs are incurred when a product line is assigned to a plant. The variable production-cost function also exhibits concavity with respect to each product-line volume. Thus both scale economies and plant focus effect are considered explicitly in the model. The model also can be used to determine which market to serve in order to best allocate the firm's resources. The problem formulation leads to a concave mixed-integer mathematical programme. Given the state of the art of non-linear programming techniques, it is often not possible to find global optima for reasonably sized problems. We develop an optimization algorithm within the framework of Benders' decomposition for the case of a piecewise linear concave cost function. Our algorithm generates optimal solutions efficiently.     

Domain decomposition in conjunction with sinc methods for Poisson's equation

Efforts to develop sinc domain decomposition methods for second-order two-point boundary-value problems have been successful, thus warranting further development of these methods. A logical first step is to thoroughly investigate the extension of these methods to Poisson's equation posed on a rectangle. The Sinc-Galerkin and sinc-collocation methods are, for appropriate weight choices, identical for Poisson's equation, and thus only the Sinc-Galerkin system is discussed here. Both the Sinc-Galerkin patching method and the Sinc-Galerkin overlapping method are presented in the simple case of decomposition into two subdomains. Numerical results are presented for each of these methods, showing the convergence. As an indication of the capabilities of these domain decomposition techniques, they are applied to Poisson's equation on an L-shaped domain. Restrictions due to the method by which the discrete system is developed require that this problem be solved using nonoverlapping subdomains. Thus only the Sinc-Galerkin patching method is presented. Numerical results are presented that show the convergence of the approximate solutions, even in the presence of boundary singularities. © 1996 John Wiley & Sons, Inc.     

Sensitivity analysis and decomposition of unreliable production lines with blocking

The analysis of finitebuffered, unreliable production lines is often based on the method of decomposition, where the original system is decomposed into a series of twostage subsystems that can be modeled as quasi birthdeath processes. In this paper, we present methods for computing the gradients of the equilibrium distribution vector for such processes. Then we consider a specific production line with finite buffers and machine breakdowns and develop an algorithm that incorporates gradient estimation into the framework of Gershwin's approximate decomposition. The algorithm is applied to the problem of workforce allocation to the machines of a production line to maximize throughput. It is shown that this problem is equivalent to a convex mathematical programming problem and, therefore, a globally optimal solution can be obtained.     

Unsteady convection and convection-diffusion problems via direct overlapping domain decomposition methods

In solving unsteady problems,domain decomposition methods may be used either for iterative preconditioning each global implicit time-step or directly (noniteratively) within a blockwise implicit time-stepping procedure, in the latter case, the inner boundary values for the subproblems are generated by explicit time-extrapolation. The overlapping variants of this method have been proved to be efficient tools for solving parabolic and first-order hyperbolic problems on modern parallel computers, because they require global communication only once per time-step. The mechanism making this possible is the exponential decay in space of the time-discrete Green's function. We investigate several model problems of convection and convection-diffusion. Favorable optimal and far-reaching estimates of the overlap required have been established in the case of exemplary standard upwind finite-difference schemes. In particular, it has been shown that the overlap for the convection-diffusion problem is the additive function of overlaps for the corresponding convection and diffusion problem to be considered independently. These results have been confirmed with several numerical test examples. © 1998 John Wiley & Sons, Inc. Numer Methods Partial Differential Eq 14: 387–406, 1998     

Half Space and Quarter Space Dirichlet Problems for the Partial Differential Equation

A customary, heuristic, method, by which the Poisson integral formula for the Dirichlet problem, for the half space, for Laplace's equation is obtained, involves Green's function, and Kelvin's method of images. Although this heuristic method leads one to guess the correct result, this Poisson formula still has to be verified directly, independently of the method by which it was arrived at, in order to be absolutely certain that a solution of the Dirichlet problem for the half space, for Laplace's equation, has been actually obtained. A similar heuristic method, as seems to be generally known, could be followed in solving the Dirichlet problem, for the half space, for the equation where is a real constant. However, in Part 1, a different, labor-saving, method is used to study Dirichlet problems for the equation. This method is essentially based on what Hadamard called the method of descent. Indeed, it is shown that he who has solved the half space Dirichlet problem for Laplace's equation has already solved the half space Dirichlet problem for the equation In Part 2, the solution formula for the quarter space Dirichlet problem for Laplace's equation is obtained from the Poisson integral formula for the half space Dirichlet problem for Laplace's equation. A representation theorem for harmonic functions in the quarter space is deduced. The method of descent is used, in Part 3, to obtain the solution formula for the quarter space Dirichlet problem for the equation by means of the solution formula for the quarter space Dirichlet problem for Laplace's equation. So that, indeed, it is also shown that he who has solved the quarter space Dirichlet problem for Laplace's equation has already solved the quarter space Dirichlet problem for the " equation" For the sake of completeness and clarity, and for the convenience of the reader, the appendix, at the end of Part 3, contains a detailed proof that the Poisson integral formula solves the half space Dirichlet problem for Laplace's equation. The Bibliography for Parts 1,2, 3 is to be found at the end of Part 1.     

A mathematical programming model and solution for scheduling production orders in Shanghai Baoshan Iron and Steel Complex

In this paper, we investigate the production order scheduling problem derived from the production of steel sheets in Shanghai Baoshan Iron and Steel Complex (Baosteel). A deterministic mixed integer programming (MIP) model for scheduling production orders on some critical and bottleneck operations in Baosteel is presented in which practical technological constraints have been considered. The objective is to determine the starting and ending times of production orders on corresponding operations under capacity constraints for minimizing the sum of weighted completion times of all orders. Due to large numbers of variables and constraints in the model, a decomposition solution methodology based on a synergistic combination of Lagrangian relaxation, linear programming and heuristics is developed. Unlike the commonly used method of relaxing capacity constraints, this methodology alternatively relaxes constraints coupling integer variables with continuous variables which are introduced to the objective function by Lagrangian multipliers. The Lagrangian relaxed problem can be decomposed into two sub-problems by separating continuous variables from integer ones. The sub-problem that relates to continuous variables is a linear programming problem which can be solved using standard software package OSL, while the other sub-problem is an integer programming problem which can be solved optimally by further decomposition. The subgradient optimization method is used to update Lagrangian multipliers. A production order scheduling simulation system for Baosteel is developed by embedding the above Lagrangian heuristics. Computational results for problems with up to 100 orders show that the proposed Lagrangian relaxation method is stable and can find good solutions within a reasonable time.     

On the convergence of cross decomposition

Cross decomposition is a recent method for mixed integer programming problems, exploiting simultaneously both the primal and the dual structure of the problem, thus combining the advantages of Dantzig—Wolfe decomposition and Benders decomposition. Finite convergence of the algorithm equipped with some simple convergence tests has been proved. Stronger convergence tests have been proposed, but not shown to yield finite convergence.In this paper cross decomposition is generalized and applied to linear programming problems, mixed integer programming problems and nonlinear programming problems (with and without linear parts). Using the stronger convergence tests finite exact convergence is shown in the first cases. Unbounded cases are discussed and also included in the convergence tests. The behaviour of the algorithm when parts of the constraint matrix are zero is also discussed. The cross decomposition procedure is generalized (by using generalized Benders decomposition) in order to enable the solution of nonlinear programming problems.     

Finiteness in restricted simplicial decomposition

Simplicial decomposition is an important form of decomposition for large non-linear programming problems with linear constraints. Von Hohenbalken has shown that if the number of retained extreme points is n + 1, where n is the number of variables in the problem, the method will reach an optimal simplex after a finite number of master problems have been solved (i.e., after a finite number of major cycles). However, on many practical problems it is infeasible to allocate computer memory for n + 1 extreme points. In this paper, we present a version of simplicial decomposition where the number of retained extreme points is restricted to r, 1 ? r ? n + 1, and prove that if r is sufficiently large, an optimal simplex will be reached in a finite number of major cycles. This result insures rapid convergence when r is properly chosen and the decomposition is implemented using a second order method to solve the master problem.     

A practical approach to approximate bilinear functions in mathematical programming problems by using Schur's decomposition and SOS type 2 variables

This paper provides a new methodology to solve bilinear, non-convex mathematical programming problems by a suitable transformation of variables. Schur's decomposition and special ordered sets (SOS) type 2 constraints are used resulting in a mixed integer linear or quadratic program in the two applications shown. While Beale, Tomlin and others developed the use of SOS type 2 variables to handle non-convexities, our approach is novel in two aspects. First, the use of Schur's decomposition as an integral part of the approximation step is new and leads to a numerically viable method to separate the variables. Second, the combination of our approach for handling bilinear side constraints in a complementarity or equilibrium problem setting is also new and opens the way to many interesting and realistic modifications to such models. We contrast our approach with other methods for solving bilinear problems also known as indefinite quadratic programs. From a practical point of view our methodology is helpful since no specialized procedures need to be created so that existing solvers can be used. The approach is illustrated with two engineering examples and the mathematical analysis appears in the Appendices.     

Using implicitly filtered RKS for generalised eigenvalue problems

The rational Krylov sequence (RKS) method can be seen as a generalisation of Arnoldi's method. It projects a matrix pencil onto a smaller subspace; this projection results in a small upper Hessenberg pencil. As for the Arnoldi method, RKS can be restarted implicitly, using the QR decomposition of a Hessenberg matrix. This restart comes with a projection of the subspace using a rational function. In this paper, it is shown how the restart can be worked out in practice. In a second part, it is shown when the filtering of the subspace basis can fail and how this failure can be handled by deflating a converged eigenvector from the subspace, using a Schur-decomposition.     

Decomposition methods for a spatial model for long-term energy pricing problem

We consider an energy production network with zones of production and transfer links. Each zone representing an energy market (a country, part of a country or a set of countries) has to satisfy the local demand using its hydro and thermal units and possibly importing and exporting using links connecting the zones. Assuming that we have the appropriate tools to solve a single zonal problem (approximate dynamic programming, dual dynamic programming, etc.), the proposed algorithm allows us to coordinate the productions of all zones. We propose two reformulations of the dynamic model which lead to different decomposition strategies. Both algorithms are adaptations of known monotone operator splitting methods, namely the alternating direction method of multipliers and the proximal decomposition algorithm which have been proved to be useful to solve convex separable optimization problems. Both algorithms present similar performance in theory but our numerical experimentation on real-size dynamic models have shown that proximal decomposition is better suited to the coordination of the zonal subproblems, becoming a natural choice to solve the dynamic optimization of the European electricity market.     

An interactive fuzzy satisficing method for structured multiobjective linear fractional programs with fuzzy numbers

In this paper, by considering the experts' vague or fuzzy understanding of the nature of the parameters in the problem formulation process, multiobjective linear fractional programming problems with block angular structure involving fuzzy numbers are formulated. Using the a-level sets of fuzzy numbers, the corresponding nonfuzzy a-multiobjective linear fractional programming problem is introduced. The fuzzy goals of the decision maker for the objective functions are quantified by eliciting the corresponding membership functions including nonlinear ones. Through the introduction of extended Pareto optimality concepts, if the decision maker specifies the degree a and the reference membership values, the corresponding extended Pareto optimal solution can be obtained by solving the minimax problems for which the Dantzig-Wolfe decomposition method and Ritter's partitioning procedure are applicable. Then a linear programming-based interactive fuzzy satisficing method with decomposition procedures for deriving a satisficing solution for the decision maker efficiently from an extended Pareto optimal solution set is presented. An illustrative numerical example is provided to demonstrate the feasibility of the proposed method.     

Homotopy perturbation method for homogeneous Smoluchowsk's equation

In this work, homotopy perturbation method (HPM) has been used to solve homogeneous Smoluchowsk's equation. The results will be compared with Adomian decomposition method (ADM). It is shown that the results of the HPM are the same as those obtained by ADM. To illustrate the reliability of the method, some special cases of the equation have been solved as examples. © 2009 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2010     

Decomposition methods for the lot-sizing and cutting-stock problems in paper industries

We investigate the one-dimensional cutting-stock problem integrated with the lot-sizing problem in the context of paper industries. The production process in paper mill industries consists of producing raw materials characterized by rolls of paper and cutting them into smaller rolls according to customer requirements. Typically, both problems are dealt with in sequence, but if the decisions concerning the cutting patterns and the production of rolls are made together, it can result in better resource management. We investigate Dantzig–Wolfe decompositions and develop column generation techniques to obtain upper and lower bounds for the integrated problem. First, we analyze the classical column generation method for the cutting-stock problem embedded in the integrated problem. Second, we propose the machine decomposition that is compared with the classical period decomposition for the lot-sizing problem. The machine decomposition model and the period decomposition model provide the same lower bound, which is recognized as being better than the linear relaxation of the classical lot-sizing model. To obtain feasible solutions, a rounding heuristic is applied after the column generation method. In addition, we propose a method that combines an adaptive large neighborhood search and column generation method, which is performed on the machine decomposition model. We carried out computational experiments on instances from the literature and on instances adapted from real-world data. The rounding heuristic applied to the first column generation method and the adaptive large neighborhood search combined with the column generation method are efficient and competitive.     

A convergence proof for linear mean value cross decomposition

The mean value cross decomposition method for linear programming problems is a modification of ordinary cross decomposition that eliminates the need for using the Benders or Dantzig-Wolfe master problem. It is a generalization of the Brown-Robinson method for a finite matrix game and can also be considered as a generalization of the Kornai-Liptak method. It is based on the subproblem phase in cross decomposition, where we iterate between the dual subproblem and the primal subproblem. As input to the dual subproblem we use the average of a part of all dual solutions of the primal subproblem, and as input to the primal subproblem we use the average of a part of all primal solutions of the dual subproblem. In this paper we give a new proof of convergence for this procedure. Previously convergence has only been shown for the application to a special separable case (which covers the Kornai-Liptak method), by showing equivalence to the Brown-Robinson method.