Solving a reverse supply chain design problem by improved Benders decomposition schemes

In this paper we propose improved Benders decomposition schemes for solving a remanufacturing supply chain design problem (RSCP). We introduce a set of valid inequalities in order to improve the quality of the lower bound and also to accelerate the convergence of the classical Benders algorithm. We also derive quasi Pareto-optimal cuts for improving convergence and propose a Benders decomposition scheme to solve our RSCP problem. Computational experiments for randomly generated networks of up to 700 sourcing sites, 100 candidate sites for locating reprocessing facilities, and 50 reclamation facilities are presented. In general, according to our computational results, the Benders decomposition scheme based on the quasi Pareto-optimal cuts outperforms the classical algorithm with valid inequalities.     

Accelerating Benders method using covering cut bundle generation

Over the years, various techniques have been proposed to speed up the classical Benders decomposition algorithm. The work presented in the literature has focused mainly on either reducing the number of iterations of the algorithm or on restricting the solution space of the decomposed problems. In this article, a new strategy for Benders algorithm is proposed and applied to two case studies in order to evaluate its efficiency. This strategy, referred to as covering cut bundle (CCB) generation, is shown to implement in a novel way the multiple constraints generation idea. The CCB generation is applied to mixed integer problems arising from two types of applications: the scheduling of crude oil and the scheduling problem for multi‐product, multi‐purpose batch plants. In both cases, CCB significantly decreases the number of iterations of the Benders method, leading to improved resolution times.     

Coordinated scheduling of production and logistics for large-scale closed-loop manufacturing using Benders decomposition optimization

This paper studies coordinated scheduling of production and logistics for a large-scale closed-loop manufacturing system by integrating its manufacturing and recycling process. In addition to the forward manufacturing process, different recycling units in reverse recycling process are also studied. A decentralized network is designed to formulate the coordinated scheduling problem as a mixed integer programming model with both binary and integer variables. As the problem for closed-loop manufacturing is large-scale and computational-consuming in nature, the model is divided into integer variable sub-models and complex binary variable sub-models for preprocessing and reprocessing respectively. An iterative solution approach by Benders decomposition is developed to accelerate the solving efficiency in large-scale case by updating custom constraints. A case study is conducted to investigate the managerial implications of the decentralized network for the closed-loop manufacturing system. Computational experiments demonstrate the validity and efficiency of the proposed iterative solution approach for the large-scale scenarios.     

Accelerating Benders stochastic decomposition for the optimization under uncertainty of the petroleum product supply chain

This paper addresses the solution of a two-stage stochastic programming model for an investment planning problem applied to the petroleum products supply chain. In this context, we present the development of acceleration techniques for the stochastic Benders decomposition that aim to strengthen the cuts generated, as well as to improve the quality of the solutions obtained during the execution of the algorithm. Computational experiments are presented for assessing the efficiency of the proposed framework. We compare the performance of the proposed algorithm with two other acceleration techniques. Results suggest that the proposed approach is able to efficiently solve the problem under consideration, achieving better performance in terms of computational times when compared to other two techniques.     

Parking buses in a depot using block patterns: A Benders decomposition approach for minimizing type mismatches

In a transit authority bus depot, buses of different types arrive in the evening to be parked in the depot for the night, and then dispatched in the morning to a set of routes, each of which requests a specific bus type. A type mismatch occurs when the requested type is not assigned to a morning route. We consider the problem of assigning the buses to the depot parking slots such that the number of mismatches is minimized, under the constraint that the buses cannot be repositioned overnight. As in Hamdouni et al. [Dispatching buses in a depot using block patterns. Technical Report, Les Cahiers du GERAD G-2004-51, HEC Montreal, Montreal, Canada, 2004, Transportation Science, to appear], we seek robust solutions by assigning a block pattern to each depot. This pattern partitions the lane into at most two blocks, each block containing buses of a given type. Since it may not be possible to respect the selected block patterns, the problem also involves a second objective which is to minimize the discrepancy between the bus type assignment to the parking slots and the block patterns. In this paper, we first study the simplified case where only the second objective is taken into account. We model this simplified problem as an integer linear program and show that practical instances of it can easily be solved using a commercial MIP solver. Then we formulate the general case as an extension of the simplified model and propose to solve it with a Benders decomposition approach embedded in a branch-and-bound procedure. This procedure is required because the Benders decomposition yields a subproblem with integrality constraints. Of particular interests, we develop strong pruning criteria and an innovative branching strategy that imposes decisions on the master problem variables which already take integer values. Computational results for the general case are also reported.     

Models for the two‐dimensional rectangular single large placement problem with guillotine cuts and constrained pattern

In this paper, we address the constrained two‐dimensional rectangular guillotine single large placement problem (2D_R_CG_SLOPP). This problem involves cutting a rectangular object to produce smaller rectangular items from orthogonal guillotine cuts. In addition, there is an upper limit on the number of copies that can be produced of each item type. To model this problem, we propose a new pseudopolynomial integer nonlinear programming (INLP) formulation and obtain an equivalent integer linear programming (ILP) formulation from it. Additionally, we developed a procedure to reduce the numbers of variables and constraints of the integer linear programming (ILP) formulation, without loss of optimality. From the ILP formulation, we derive two new pseudopolynomial models for particular cases of the 2D_R_CG_SLOPP, which consider only two‐staged or one‐group patterns. Finally, as a specific solution method for the 2D_R_CG_SLOPP, we apply Benders decomposition to the proposed ILP formulation and develop a branch‐and‐Benders‐cut algorithm. All proposed approaches are evaluated through computational experiments using benchmark instances and compared with other formulations available in the literature. The results show that the new formulations are appropriate in scenarios characterized by few item types that are large with respect to the object's dimensions.