Plant location and procurement planning in knockdown production systems

We consider an integrated problem of plant location and capacity planning for components procurement in knockdown production systems. The problem is that of determining the schedule of opening components manufacturing plants, plans for acquisition of capacities in opened components manufacturing plants, and plans for components procurement in final assembly plants with the objective of minimizing the sum of fixed costs for opening plants, acquisition and operation costs of facilities, and delivery and subcontracting costs of components. The problem is formulated as a mixed integer linear program and solved by a two-stage solution procedure. In the solution procedure, the problem is decomposed into two tractable subproblems and these subproblems are solved sequentially. In the first stage, a dynamic plant location problem is solved using a cut and branch algorithm based on Gomory cuts, while a multiperiod capacity planning problem is solved in the second stage by a heuristic algorithm that uses a cut and branch algorithm and a variable reduction scheme. The solution procedure is tested on problems of a practical size and results show that the procedure gives reasonably good solutions.     

Optimal and heuristic algorithms for multiproduct uncapacitated facility location

We consider a generalization of the classic uncapacitated facility location problem (UFLP) in which customers require multiple products. We call this the multiproduct uncapacitated facility location problem (MUFLP). In MUFLP, in addition to a fixed cost for opening a facility, a fixed cost is incurred for each product that a facility is equipped to handle. Also, an assignment cost is incurred for satisfying a customer's requirement for a particular product at a chosen facility. We describe a branch-and-bound algorithm for MUFLP. Lower bounds are obtained by solving a UFLP subproblem for each product using a dual ascent routine. We also describe a heuristic branch-and-bound procedure in which the solutions to the subproblems at a given node might not generate a true lower bound. To generate a feasible solution, a ‘superposition’ heuristic based on solving UFLP subproblems for each product, as well as a ‘drop’ heuristic that eliminates facilities and equipment from the solution in a step-by-step manner, are given. Computational results are reported.     

Single-vendor multi-buyer inventory coordination under private information

This paper considers the problem of coordinating a single-vendor multi-buyer inventory system when there are privacy restrictions in the information required to solve the problem. The objective function and cost parameters of each facility are regarded as private information that no other facilities in the system have access to. Moreover, each facility is responsible to specify its own replenishment policy. The objective is to minimize the total average setup/ordering and inventory-related cost. Solution methodologies under private and global information are developed to find two types of nested power-of-two stationary policies. The first policy assumes all the buyers must replenish simultaneously. The second policy is a more general case where the common replenishment assumption is relaxed. A simple form of information exchange is uncovered that allows the solution methodologies for private and global information yield the same results. The experimental results suggest that the performance of the proposed heuristics is comparable or better than an existing method.     

A reduction result for location problems with polyhedral barriers

In this paper we consider the problem of locating one new facility in the plane with respect to a given set of existing facilities where a set of polyhedral barriers restricts traveling. This non-convex optimization problem can be reduced to a finite set of convex subproblems if the objective function is a convex function of the travel distances between the new and the existing facilities (like e.g. the median and center objective functions). An exact algorithm and a heuristic solution procedure based on this reduction result are developed.     

Capacitated emergency facility siting with multiple levels of backup

In many service systems, the primary objective is to provide continuous service and/or service within a prespecified time interval. In the public sector, emergency service systems fit into this category. In the private sector, systems providing repair service to critical production facilities and computers constitute another example. In these systems, the concept of multiple service facilities providing backup to each other becomes an important element in the design process. In this paper, we study the capacitated facility siting problem with multiple levels of backup coverage. The problem is formulated as a mathematical program; an efficient solution procedure is developed and computational experiments are reported.     

An efficient solution method for Weber problems with barriers based on genetic algorithms

In this paper we consider the problem of locating one new facility with respect to a given set of existing facilities in the plane and in the presence of convex polyhedral barriers. It is assumed that a barrier is a region where neither facility location nor travelling are permitted. The resulting non-convex optimization problem can be reduced to a finite series of convex subproblems, which can be solved by the Weiszfeld algorithm in case of the Weber objective function and Euclidean distances. A solution method is presented that, by iteratively executing a genetic algorithm for the selection of subproblems, quickly finds a solution of the global problem. Visibility arguments are used to reduce the number of subproblems that need to be considered, and numerical examples are presented.     

Single machine earliness and tardiness scheduling

We examine the problem of scheduling a given set of jobs on a single machine to minimize total early and tardy costs without considering machine idle time. We decompose the problem into two subproblems with a simpler structure. Then the lower bound of the problem is the sum of the lower bounds of two subproblems. A lower bound of each subproblem is obtained by Lagrangian relaxation. Rather than using the well-known subgradient optimization approach, we develop two efficient multiplier adjustment procedures with complexity O(nlog n) to solve two Lagrangian dual subproblems. A branch-and-bound algorithm based on the two efficient procedures is presented, and is used to solve problems with up to 50 jobs, hence doubling the size of problems that can be solved by existing branch-and-bound algorithms. We also propose a heuristic procedure based on the neighborhood search approach. The computational results for problems with up to 3 000 jobs show that the heuristic procedure performs much better than known heuristics for this problem in terms of both solution efficiency and quality. In addition, the results establish the effectiveness of the heuristic procedure in solving realistic problems to optimality or near optimality.     

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.     

Using conical partition to globally maximizing the nonlinear sum of ratios

This article presents a global optimization algorithm for globally maximizing the sum of concave–convex ratios problem with a convex feasible region. The algorithm uses a branch and bound scheme where a concave envelope of the objective function is constructed to obtain an upper bound of the optimal value by using conical partition. As a result, the upper-bound subproblems during the algorithm search are all ordinary convex programs with less variables and constraints and do not grow in size from iterations to iterations in the computation procedure, and furthermore a new bounding tightening strategy is proposed such that the upper-bound convex relaxation subproblems are closer to the original nonconvex problem to enhance solution procedure. At last, some numerical examples are given to vindicate our conclusions.     

A Representation and Economic Interpretation of a Two-Level Programming Problem

This paper first presents a formulation for a class of hierarchial problems that show a two-stage decision making process; this formulation is termed multilevel programming and could be defined, in general, as a mathematical programming problem (master) containing other multilevel programs in the constraints (subproblems). A two-level problem is analyzed in detail, and we develop a solution procedure that replaces the subproblem by its Kuhn-Tucker conditions and then further transforms it into a mixed integer quadratic programming problem by exploiting the disjunctive nature of the complementary slackness conditions.An example problem is solved and the economic implications of the formulation and its solution are reviewed.     

一类抛物型方程组的特征修正区域分解有限元方法

在实际生产和科学研究中,有许多物理问题的数学模型为抛物型方程组问题,如可压缩核废料污染问题,地下水资源问题,杨青提出了差分格式和有限元格式,应用先验估计得到了最优的l^2和L^2模误差估计,江城顺等利用交替方向有限元方法得到了H^1模和L^2模误差估计．杨国强等采用显式可解的三层差分格式求解二维方程组得到了H^1模误差估计．     

A Dual Simplex Implementation of a Constraint Selection Algorithm for Linear Programming

The constraint selection approach to linear programming begins by solving a relaxed version of the problem using only a few of the original constraints. If the solution obtained to this relaxation satisfies the remaining constraints it is optimal for the original LP. Otherwise, additional constraints must be incorporated in a larger relaxation. The procedure successively generates larger subproblems until an optimal solution is obtained which satisfies all of the original constraints. Computational results for a dual simplex implementation of this technique indicate that solving several small subproblems in this manner is more computationally efficient than solving the original LP using the revised simplex method.     

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.     

Medium-term hydro-thermal coordination via hydro and thermal subsystem decomposition

Summary This paper addresses the medium-term hydro-thermal coordination problem in an electric energy system. That is, the problem of finding the energy production of every power plant (hydro or thermal) in every subperiod of a given planning period, so that the customer load is supplied at minimum cost. The planning horizon is typically one to two months and the first week of this planning period is modeled in detail. The solution method proposed decomposes the problem in two subproblems corresponding to the hydro and thermal subsystems. These two subproblems are coordinated using a coordinating function for every subperiod. The coordinating function of a given subperiod expresses total production cost in that subperiod as a function of the total hydro production in that subperiod. The decomposition proposed makes it possible to use specialized algorithms to solve the hydro and thermal subproblems. This results in a very efficient computational procedure. From an experimental point of view the coordinating mechanism is robust. A case study is provided. It considers 61 thermal plants, a hydro system including 8 cascaded hydro plants and a 48 subperiods planning period.     

The continuous collapsing Knapsack problem

A Collapsing Knapsack is a container whose capacity diminishes as the number of items it must hold is increased. This paper focuses on those cases in which the decision variables are continuous, i.e., can take any non-negative value. It is demonstrated that the problem can be reduced to a set of two dimensional subproblems. Strategies for elimination of subproblems and conditions permitting reduction to a set of one dimensional problems are also considered. Computational results indicate that the procedure is quite efficient. Even for large problems only a small number of subproblems have to be solved.     

AN EFFECTIVE SEQUENTIAL QUADRATIC PROGRAMMING ALGORITHM FOR NONLINEAR OPTIMIZATION PROBLEMS

In this paper,a new globally convergent algorithm for nonlinear optimization prablems with equality and inequality constraints is presented. The new algorithm is of SQP type which determines a search direction by solving a quadratic programming subproblem per itera-tion. Some revisions on the quadratic programming subproblem have been made in such a way that the associated constraint region is nonempty for each point x generated by the algorithm, i. e. , the subproblems always have optimal solutions. The new algorithm has two important properties. The computation of revision parameter for guaranteeing the consistency of quadratic sub-problem and the computation of the second order correction step for superlinear convergence use the same inverse of a matrix per iteration, so the computation amount of the new algorithm will not be increased much more than other SQP type algorithms; Another is that the new algorithm can give automatically a feasible point as a starting point for the quadratic subproblems pe     

A Linear Programming Approach to the Solution of Constrained Multi-Facility Minimax Location Problems where Distances are Rectangular

The problem of locating new facilities with respect to existing facilities is stated as a linear programming problem where inter-facility distances are assumed to be rectangular. The criterion of location is the minimization of the maximum weighted rectangular distance in the system. Linear constraints which (a) limit the new facility locations and (b) enforce upper bounds on the distances between new and existing facilities and between new facilities can be included. The dual programming problem is formulated in order to provide for an efficient solution procedure. It is shown that the duLal variables provide information abouLt the complete range of new facility locations which satisfy the minimax criterion.     

A heuristic method for the multi-story layout problem

In this paper we present a heuristic procedure designed expressly for solving a large layout problem in a multi-story setting, where the objective is to minimize total fixed and interaction costs. This is achieved by decomposing the original facilities layout problem into several similar but smaller problems, thus enabling solution of problems with as many as 150 facilities in reasonable time. Some of the novel features of the procedure described are the use of a heuristic K-median subroutine to obtain groupings of facilities, and a simple and fast exchange-improvement method. Computational results for randomly generated problems compare the effectiveness of this method with the space planning heuristic method of Liggett and Mitchell.