Master problem

The only way to traly master problem-solving is to practice problems every day, consistently. You will never learn how to solve problems by just reading a book. You must try, and fail, and try again. You must learn from your mistakes. You must get frustrated when you can t solve a problem. That s the learning process. Whenever you encounter an exercise in this book, pick up a pencil and work on it. Don t skip over the problems They are designed to foster skills necessary for problem-solving. 

The formulation for this scenario entails 1411 constraints, 511 continuous and 120 binary variables. The reduction in continuous variables compared to scenario 1 is due to the absence of linearization variables, since no attempt was made to linearize the scenario 2 model as explained in Section 4.3. An average of 1100 nodes were explored in the branch and bound search tree during the three major iterations between the MILP master problem and the NLP subproblem. The problem was solved in 6.54 CPU seconds resulting in an optimal objective of 2052.31 kg, which corresponds to 13% reduction in freshwater requirement. The corresponding water recycle/reuse network is shown in Fig. 4.10. 

As shown in Table 4.4, the model for scenario 2, which is a nonconvex MINLP, consists of 1195 constraints, 352 continuous and 70 binary variables. An average of 151 nodes were explored in the branch and bound algorithm over the 3 major iterations between the MILP master problem and NLP subproblems. The problem was solved in 2.48 CPU seconds with an objective value of 1.67 million. Whilst the product quantity is the same as in scenario 1, i.e. 850 t, the water requirement is only 185 t, which corresponds to 52.56% reduction in freshwater requirement. The water network to achieve this target is shown in Fig. 4.15. 

The main idea of stage decomposition (see Figure 9.10) is to remove the ties between the scenario subproblems of the 2S-MILP by fixing the first-stage variables. The 2S-MILP is written in its intensive form [9], where the resulting master problem is... 

The hybrid evolutionary algorithm for 2S-MILPs is realized by using an evolution strategy (ES) to solve the master problem of the intensive 2S-MILP. Each individual of the ES represents a first-stage candidate solution x. The object parameters are encoded by a mixed-integer vector. The fitness of an individual is evaluated by the objective function of the master problem (MASTER),/ (x). 

Flowsheet optimization is also regarded as a key task in the structural optimization of a flowsheet. As a described in the introduction, structural optimization for process design can be formulated as a mixed integer nonlinear program (MINLP). This then allows for addition or replacement of existing units, and consideration of a number of design options simultaneously. In these formulations individual units are turned on and off over the course of the optimization, as suggested by the MINLP master problem. 

The modeling system GAMS (Brooke et al., 1996) is used for setting up the optimization models. The computational tests were carried out on a Pentium M processor 2.13 GHz. The models were solved with DICOPT (Viswanathan and Gross-mann, 1990). The NLP subproblems were solved with CONOPT2 (Drud, 1994), while the MILP master problems were solved with CPLEX (CPLEX Optimization Inc, 1993). 

The basic idea in Generalized Benders Decomposition GBD is the generation, at each iteration, of an upper bound and a lower bound on the sought solution of the MINLP model. The upper bound results from the primal problem, while the lower bound results from the master problem. The primal problem corresponds to problem (6.2) with fixed y-variables (i.e., it is in the jr-space only), and its solution provides information about the upper bound and the Lagrange... 

This section presents the theoretical development of the Generalized Benders Decomposition GBD. The primal problem is analyzed first for the feasible and infeasible cases. Subsequently, the theoretical analysis for the derivation of the master problem is presented. 

The derivation of the master problem in the GBD makes use of nonlinear duality theory and is characterized by the following three key ideas ... 

Remark 9 Note that the master problem (M) is equivalent to (6.2). It involves, however, an infinite number of constraints, and hence we would need to consider a relaxation of the master (e.g., by dropping a number of constraints) which will represent a lower bound on the original problem. Note also that the master problem features an outer optimization problem with respect toy 6 Y and inner optimization problems with respect to x which are in fact parametric in y. It is this outer-inner nature that makes the solution of even a relaxed master problem difficult. 

Remark 10 (Geometric Interpretation of the Master Problem) The inner minimization problems... 

If the support functions are linear iny, then the master problem approximates v(y) by tangent hyperplanes and we can conclude that v(y) is convex iny. Note that v(y) can be convex iny even though problem (6.2) is nonconvex in the jointx-y space Floudas and Visweswaran (1990). 

In the previous section we discussed the primal and master problem for the GBD. We have the primal problem being a (linear or) nonlinear programming NLP problem that can be solved via available local NLP solvers (e.g., MINOS 5.3). The master problem, however, consists of outer and inner optimization problems, and approaches towards attaining its solution are discussed in the following. 

The master problem has as constraints the two inner optimization problems (i.e., for the case of feasible primal and infeasible primal problems) which, however, need to be considered for all A and all p > 0 (i.e., feasible primal) and all (A, p) A (i.e., infeasible). This implies that the master problem has a very large number of constraints. 

Let (y,pB) be an optimal solution of the above relaxed master problem. pB is a lower bound on problem (6.2) that is, the current lower bound is LBD = pB. If UBD — LBD < e, then terminate. 

Remark 4 Note that the relaxed master problem (see step 2) in the first iteration will have as a constraint one support function that corresponds to feasible primal and will be of the form ... 

Note that in this case, the relaxed master problem (6.12) will have a solution that is greater or equal to the solution of (6.11). This is due to having the additional constraint. Therefore, we can see that the sequence of lower bounds that is created from the solution of the relaxed master problems is nondecreasing. A similar argument holds true in the case of having infeasible primal in the second iteration. 

Remark 6 The termination criterion for GBD is based on the difference between the updated upper bound and the current lower bound. If this difference is less than or equal to a prespecified tolerance e > 0 then we terminate. Note though that if we introduce in the relaxed master integer cuts that exclude the previously found 0-1 combinations, then the termination criterion can be met by having found an infeasible master problem (i.e., there is no 0-1 combination that makes it feasible). 

If they variables participate separably but in a nonlinear way, then the relaxed master problem is of 0-1 nonlinear programming type. 

Based on the previously presented analysis for the vl-GBD under the separability assumption, we can now formulate the relaxed master problem in an explicit form. 

Remark 1 Note that since y Y = 0 - 1, the master problem is a 0-1 programming problem with one scalar variable pB. If they variables participate linearly, then it is a 0-1 linear problem which can be solved with standard branch and bound algorithms. In such a case, we can introduce integer cuts of the form ... 

Note that the third and fourth constraint have only 0-1 variables and hence can be moved directly to the relaxed master problem. 

This additional assumption was made so as to create special structure not only in the primal but also in the relaxed master problem. The type of special structure in the relaxed master problem has to do with its convexity characteristics. 

The basic idea in GOS is to select the x andy variables in a such a way that the primal and the relaxed master problem of the v2-GBD satisfy the appropriate convexity requirements and hence attain their respective global solutions. 

---