Integrated supply chain planning under uncertainty using an improved stochastic approach

This paper proposes an integrated model and a modified solution method for solving supply chain network design problems under uncertainty. The stochastic supply chain network design model is provided as a two-stage stochastic program where the two stages in the decision-making process correspond to the strategic and tactical decisions. The uncertainties are mostly found in the tactical stage because most tactical parameters are not fully known when the strategic decisions have to be made. The main uncertain parameters are the operational costs, the customer demand and capacity of the facilities. In the improved solution method, the sample average approximation technique is integrated with the accelerated Benders’ decomposition approach to improvement of the mixed integer linear programming solution phase. The surrogate constraints method will be utilized to acceleration of the decomposition algorithm. A computational study on randomly generated data sets is presented to highlight the efficiency of the proposed solution method. The computational results show that the modified sample average approximation method effectively expedites the computational procedure in comparison with the original approach.     

Optimizing the supply chain configuration for make-to-order manufacturing

We consider a make-to-order (MTO) manufacturer who has won multiple contracts with specified quantities to be delivered by certain due dates. Before production starts, the company must configure its supply chain and make sourcing decisions. It also needs to plan the starting time for each production task under limited availability of resources such as machines and workforce. We develop a model for simultaneously optimizing such sourcing and planning decisions while exploiting their tradeoffs. The resulting multi-mode resource-constrained project scheduling problem (MMRCPSP) with a nonlinear objective function is NP-complete. To efficiently solve it, a hybrid Benders decomposition (HBD) algorithm combining the strengths of both mathematical programming and constraint programming is developed. The HBD exploits the structure of the model formulation and decomposes it into a relaxed master problem handled by mixed-integer nonlinear programming (MINLP), and a scheduling feasibility sub-problem handled by constraint programming (CP). Cuts are iteratively generated by solving the feasibility sub-problem and added back to the relaxed master problem, until an optimal solution is found or infeasibility is proved. Computational experiments are conducted to examine performance of the model and algorithm. Insights about optimal configuration of MTO supply chains are drawn and discussed.     

A constraint generation scheme to probabilistic linear problems with an application to power system expansion planning

In this paper, we first describe a constraint generation scheme for probabilistic mixed integer programming problems. Next, we present a decomposition approach to the peak capacity expansion planning of interconnected hydrothermal generating systems, with bounds on the transmission capacity between the regions. The objective is to minimize investments in generating units and interconnection links, subject to constraints on supply reliability. The problem is formulated as a stochastic integer program. The constraint generation scheme, which is similar to Benders decomposition, is applied in the solution of the peak capacity expansion problem. The master problem in this decomposition scheme is an integer program, solved by implicit enumeration. The operating subproblem corresponds to a stochastic network flow problem, and is solved by a maximum flow algorithm and Monte Carlo simulation. The approach is illustrated through a case study involving the expansion of the system of the Brazilian Southeastern region.     

Stochastic programming for nurse assignment

We present a brief overview of four phases of nurse planning. For the last phase, which assigns nurses to patients, a stochastic integer programming model is developed. A Benders’ decomposition approach is proposed to solve this problem, and a greedy algorithm is employed to solve the recourse subproblem. To improve the efficiency of the algorithm, we introduce sets of valid inequalities to strengthen a relaxed master problem. Computational results are provided based upon data from Baylor Regional Medical Center in Grapevine, Texas. Finally, areas of future research are discussed.     

Solving a capacitated hub location problem

In this paper we address a problem consisting of determining the routes and the hubs to be used in order to send, at minimum cost, a set of commodities from sources to destinations in a given capacitated network. The capacities and costs of the arcs and hubs are given, and the arcs connecting the hubs are not assumed to create a complete graph. We present a mixed integer linear programming formulation and describe two branch-and-cut algorithms based on decomposition techniques. We evaluate and compare these algorithms on instances with up to 25 commodities and 10 potential hubs. One of the contributions of this paper is to show that a Double Benders’ Decomposition approach outperforms the standard Benders’ Decomposition, which has been widely used in recent articles on similar problems. For larger instances we propose a heuristic approach based on a linear programming relaxation of the mixed integer model. The heuristic turns out to be very effective and the results of our computational experiments show that near-optimal solutions can be derived rapidly.     

Column enumeration based decomposition techniques for a class of non-convex MINLP problems

We propose a decomposition algorithm for a special class of nonconvex mixed integer nonlinear programming problems which have an assignment constraint. If the assignment decisions are decoupled from the remaining constraints of the optimization problem, we propose to use a column enumeration approach. The master problem is a partitioning problem whose objective function coefficients are computed via subproblems. These problems can be linear, mixed integer linear, (non-)convex nonlinear, or mixed integer nonlinear. However, the important property of the subproblems is that we can compute their exact global optimum quickly. The proposed technique will be illustrated solving a cutting problem with optimum nonlinear programming subproblems.     

Furniture supply chain tactical planning optimization using a time decomposition approach

We study the supply chain tactical planning problem of an integrated furniture company located in the Province of Québec, Canada. The paper presents a mathematical model for tactical planning of a subset of the supply chain. The decisions concern procurement, inventory, outsourcing and demand allocation policies. The goal is to define manufacturing and logistics policies that will allow the furniture company to have a competitive level of service at minimum cost. We consider planning horizon of 1 year and the time periods are based on weeks. We assume that customer’s demand is known and dynamic over the planning horizon. Supply chain planning is formulated as a large mixed integer programming model. We developed a heuristic using a time decomposition approach in order to obtain good solutions within reasonable time limit for large size problems. Computational results of the heuristic are reported. We also present the quantitative and qualitative results of the application of the mathematical model to a real industrial case.     

Benders's method revisited

The master problem in Benders's partitioning method is an integer program with a very large number of constraints, each of which is usually generated by solving the integer program with the constraints generated earlier. Computational experience shows that the subset B of those constraints of the master problem that are satisfied with equality at the linear programming optimum often play a crucial role in determining the integer optimum, in the sense that only a few of the remaining inequalities are needed. We characterize this subset B of inequalities. If an optimal basic solution to the linear program is nondegenerate in the continuous variables and has p integer-constrained basic variables, then the corresponding set B contains at most 2^p inequalities, none of which is implied by the others. We give an efficient procedure for generating an appropriate subset of the inequalities in B, which leads to a considerably improved version of Benders's method.     

Robust optimization for interactive multiobjective programming with imprecise information applied to R&D project portfolio selection

A multiobjective binary integer programming model for R&D project portfolio selection with competing objectives is developed when problem coefficients in both objective functions and constraints are uncertain. Robust optimization is used in dealing with uncertainty while an interactive procedure is used in making tradeoffs among the multiple objectives. Robust nondominated solutions are generated by solving the linearized counterpart of the robust augmented weighted Tchebycheff programs. A decision maker’s most preferred solution is identified in the interactive robust weighted Tchebycheff procedure by progressively eliciting and incorporating the decision maker’s preference information into the solution process. An example is presented to illustrate the solution approach and performance. The developed approach can also be applied to general multiobjective mixed integer programming problems.     

Incorporating inventory and routing costs in strategic location models

We consider a supply chain design problem where the decision maker needs to decide the number and locations of the distribution centers (DCs). Customers face random demand, and each DC maintains a certain amount of safety stock in order to achieve a certain service level for the customers it serves. The objective is to minimize the total cost that includes location costs and inventory costs at the DCs, and distribution costs in the supply chain. We show that this problem can be formulated as a nonlinear integer programming model, for which we propose a Lagrangian relaxation based solution algorithm. By exploring the structure of the problem, we find a low-order polynomial algorithm for the nonlinear integer programming problem that must be solved in solving the Lagrangian relaxation sub-problems. We present computational results for several instances of the problem with sizes ranging from 40 to 320 customers. Our results show the benefits of having an integrated supply chain design framework that includes location, inventory, and routing decisions in the same optimization model.     

Applying oracles of on-demand accuracy in two-stage stochastic programming – A computational study

Traditionally, two variants of the L-shaped method based on Benders’ decomposition principle are used to solve two-stage stochastic programming problems: the aggregate and the disaggregate version. In this study we report our experiments with a special convex programming method applied to the aggregate master problem. The convex programming method is of the type that uses an oracle with on-demand accuracy. We use a special form which, when applied to two-stage stochastic programming problems, is shown to integrate the advantages of the traditional variants while avoiding their disadvantages. On a set of 105 test problems, we compare and analyze parallel implementations of regularized and unregularized versions of the algorithms. The results indicate that solution times are significantly shortened by applying the concept of on-demand accuracy.     

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.     

An approach to the valuation and decision of ERP investment projects based on real options

The risks and uncertainties inherent in most enterprise resources planning (ERP) investment projects are vast. Decision making in multistage ERP projects investment is also complex, due mainly to the uncertainties involved and the various managerial and/or physical constraints to be enforced. This paper tackles the problem using a real-option analysis framework, and applies multistage stochastic integer programming in formulating an analytical model whose solution will yield optimum or near-optimum investment decisions for ERP projects. Traditionally, such decision problems were tackled using lattice simulation or finite difference methods to compute the value of simple real options. However, these approaches are incapable of dealing with the more complex compound real options, and their use is thus limited to simple real-option analysis. Multistage stochastic integer programming is particularly suitable for sequential decision making under uncertainty, and is used in this paper and to find near-optimal strategies for complex decision problems. Compared with the traditional approaches, multistage stochastic integer programming is a much more powerful tool in evaluating such compound real options. This paper describes the proposed real-option analysis model and uses an example case study to demonstrate the effectiveness of the proposed approach.     

Fair transfer price and inventory holding policies in two-enterprise supply chains

A key issue in supply chain optimisation involving multiple enterprises is the determination of policies that optimise the performance of the supply chain as a whole while ensuring adequate rewards for each participant.In this paper, we present a mathematical programming formulation for fair, optimised profit distribution between echelons in a general multi-enterprise supply chain. The proposed formulation is based on an approach applying the Nash bargaining solution for finding optimal multi-partner profit levels subject to given minimum echelon profit requirements.The overall problem is first formulated as a mixed integer non-linear programming (MINLP) model. A spatial and binary variable branch-and-bound algorithm is then applied to the above problem based on exact and approximate linearisations of the bilinear terms involved in the model, while at each node of the search tree, a mixed integer linear programming (MILP) problem is solved. The solution comprises inter-firm transfer prices, production and inventory levels, flows of products between echelons, and sales profiles.The applicability of the proposed approach is demonstrated by a number of illustrative examples based on industrial processes.     

An application of Lagrangian relaxation to a capacity planning problem under uncertainty

A supply chain network-planning problem is presented as a two-stage resource allocation model with 0-1 discrete variables. In contrast to the deterministic mathematical programming approach, we use scenarios, to represent the uncertainties in demand. This formulation leads to a very large scale mixed integer-programming problem which is intractable. We apply Lagrangian relaxation and its corresponding decomposition of the initial problem in a novel way, whereby the Lagrangian relaxation is reinterpreted as a column generator and the integer feasible solutions are used to approximate the given problem. This approach addresses two closely related problems of scenario analysis and two-stage stochastic programs. Computational solutions for large data instances of these problems are carried out successfully and their solutions analysed and reported. The model and the solution system have been applied to study supply chain capacity investment and planning.     

Cost optimal allocation of rail passenger lines

We consider the problem of cost optimal railway line allocation for passenger trains for the Dutch railway system. At present, the allocation of passenger lines by Dutch Railways is based on maximizing the number of direct travelers. This paper develops an alternative approach that takes operating costs into account. A mathematical programming model is developed which minimizes the operating costs subject to service constraints and capacity requirements. The model optimizes on lines, line types, routes, frequencies and train lengths. First, the line allocation model is formulated as an integer nonlinear programming model. This model is transformed into an integer linear programming model with binary decision variables. An algorithm is presented which solves the problem to optimality. The algorithm is based upon constraint satisfaction and a Branch and Bound procedure. The algorithm is applied to a subnetwork of the Dutch railway system for which it shows a substantial cost reduction. Further application and extension seem promising.     

基于交互式模糊规划方法的可持续闭环供应链网络规划

在市场需求、设施开设成本和产品回收率不确定的条件下,采用一种交互式可能性规划方法,研究由多个工厂、分销点、市场和废旧点构成的可持续闭环供应链网络设计问题。基于可持续闭环供应链网络结构,构建以企业运营成本和环境伤害最小、社会效益最大为目标的混合整数规划模型。同时,引入改进Epsilon约束方法将多目标优化问题转化为单目标优化问题,在此基础上提出一种两阶段可能性规划方法,基于TH模糊方法对不确定性参数进行处理。最后,通过数值实例,验证本文所建可持续闭环供应链网络模型的有效性,并对悲观-乐观值、不确定参数最低可接受水平β、可调参数γ进行敏感性分析;通过与其他模糊方法对比表明,采用TH模糊方法能得到稳定的最优解。     

Zero-one integer programs with few constraints —Lower bounding theory

The zero-one integer programming problem and its special case, the multiconstraint knapsack problem frequently appear as subproblems in many combinatorial optimization problems. We present several methods for computing lower bounds on the optimal solution of the zero-one integer programming problem. They include Lagrangean, surrogate and composite relaxations. New heuristic procedures are suggested for determining good surrogate multipliers. Based on theoretical results and extensive computational testing, it is shown that for zero-one integer problems with few constraints surrogate relaxation is a viable alternative to the commonly used Lagrangean and linear programming relaxations. These results are used in a follow up paper to develop an efficient branch and bound algorithm for solving zero-one integer programming problems.