China
Africa
Explore chapters and articles related to this topic
Long-Range Planning of Chemical Manufacturing Systems
Published in Cornelius Leondes, The Design of Manufacturing Systems, 2019
Shabbir Ahmed, Nikolaos V. Sahinidis
Benders decomposition is a standard decomposition technique in which the MILP problem is solved through a sequence of LP subproblems in the “easy” variables and MILP master problem in the “complicating” variables [3]. The subproblems provide lower bounds to the net present value while the master problem provides upper bounds. The definition of the LP subproblems and the MILP master problem depends on the partitioning of the variables. The natural choice for this partitioning is Complicating variables for the master problem: u = [yit].Remaining variables for the LP subproblems: v = [Eit, Pjlt, Qit, Sjlt, Wit].
Methodology
Published in Tolga Bektaş, Freight Transport and Distribution, 2017
Benders decomposition (Benders, 1962) is a technique that partitions the model into two sets of variables, where one set induces smaller formulation called the subproblem, and the other set forms what is commonly named the master problem. There may be different ways of partitioning the variables of the original formulation, which in turn would give rise to different subproblems and master problems. Often, the formulation itself suggests a natural partitioning of the variables, such as x and y in model M. In linear programming formulations, the partitioning of the variables can be made to correspond to two separate sets of decisions they represent. In mixed-integer linear programming formulations, it is customary to partition the variables such that the integer variables are separated from their continuous counterpart. However, these are not requirements but merely rules of thumb.
Generating optimal robust continuous piecewise linear regression with outliers through combinatorial Benders decomposition
Published in IISE Transactions, 2023
John Alasdair Warwicker, Steffen Rebennack
We use Benders decomposition (Benders, 1962) to look for speedups in the updated, robust formulation to mitigate the weakness presented by the presence of big- constructs. The Benders decomposition approach allows for linear programming problems with a certain structure to be optimised via a divide-and-conquer approach (Rebennack, 2016b; Rahmaniani et al.,2017). Benders decomposition also works for MILP models as long as the sub problems remain linear. Since the computational difficulty of solving an optimization problem increases with the size of the problem, iteratively solving sub problems can be more efficient than solving the main, monolithic problem. The sub problems feed information and constraints to the master problem. The given MILP model fits this structure well, since the problem can be separated into a master problem solved over the first set of variables (i.e., binary variables), and a sub problem over the continuous variables. Depending on the optimality (or infeasibility) of the sub problem, so-called Benders cuts are implemented into the master problem, which is re-solved until no more cuts are available. However, for the MILP we consider, we expect (and observe in experimental results) that the Benders cuts are weak due to the presence of big- values and the number of constraints (Codato and Fischetti, 2006). Improvements to the Benders decomposition algorithm have been sought since its inception (see the survey by Rei et al. (2009) for an in-depth discussion).
An exact method for job sequencing in a mixed-model assembly line considering feeding lines based on the Benders decomposition approach
Published in International Journal of Management Science and Engineering Management, 2022
Anis Saadi, Parviz Fattahi, Donya Rahmanii, Seyed Mohammad Hassan Hosseini, Shib Sankar Sana
In general terms, the Benders decomposition is a method that involves partitioning the linear programming model of the problem into a master problem (MP) and subproblem (SP) (Magnanti & Wong, 1981). The MP, a mixed-integer problem, determines a lower bound of the solution. On the other hand, the result of SP formulation is duality and then the remaining variables are determined. Briefly, the solution process is used to solve the MP and then transfers the results to the SP. After that, the proper solution of the SP is provided as an upper bound of the problem solution. This is an iterative process. If the SP finds that the decisions of the proposed MP are infeasible then the MP must be resolved by considering one or more additional constraints. In each iteration, the lower bound and the upper bound are updated, and if the stopping criterion is not provided we create a Benders cut generated by the dual of the SP. We add this cut to the MP and thus the iterative process continues until the stopping criterion is met. A predetermined small gap between the lower bound and the upper bound is considered to be the stopping criterion and terminates the procedure.
A stochastic programming approach for heterogeneous variable message sign location problem for freeway networks
Published in Transportmetrica A: Transport Science, 2022
Guowei Zhang, Ning Zhu, Shiquan Zhong, Shoufeng Ma, Shanshan Han
Benders decomposition is a well-known methodology proposed by Benders (1962), for solving a class of mixed-integer linear programming (MILP) problems. It has been used for many optimization problems, such as planning and scheduling (Canto 2008; Hooker 2007), transportation and telecommunications (Costa 2005), and energy and resource management (Cai et al. 2001). Instead of considering all decision variables and constraints of a large-scale problem simultaneously, the Benders decomposition method partitions the problem into a master problem and subproblems, which can be solved efficiently. The subproblem is then dualized, and the associated extreme rays and points respectively define the feasibility cuts and optimality cuts. Since the number of extreme rays and points can be huge, it is impossible to enumerate all of them. Thus, an iterative algorithm is developed. In particular, at each iteration, a feasibility or optimality cut is generated by solving the subproblem, and it is added to the master problem, until an optimal solution is found. Thus, to confirm the convergence, the optimality gap can be calculated at each iteration, in which the lower and upper bound are provided by the master problem and subproblem respectively. A recent review (Rahmaniani et al. 2017) provides more details of Benders decomposition.