Academy Offer

Extended to August 15

Claim a 20% discount on all eLearning and virtual courses purchases with code EDU20OFF.

This promotion does not apply to the credential programs.

Alternative Regularization Schemes in Outer-Approximation Algorithms for Convex MINLP

  • Checkout

    Checkout

    Do you already own this?

    Pricing


    Individuals

    AIChE Member Credits 0.5
    AIChE Members $19.00
    AIChE Graduate Student Members Free
    AIChE Undergraduate Student Members Free
    Non-Members $29.00
  • Type:
    Conference Presentation
  • Conference Type:
    AIChE Annual Meeting
  • Presentation Date:
    November 9, 2021
  • Duration:
    19 minutes
  • Skill Level:
    Intermediate
  • PDHs:
    0.50

Share This Post:

Optimization problems involving nonlinear constraints, and both discrete and continuous variables, have proved to provide a remarkably versatile modeling paradigm. These optimization problems, Mixed-integer nonlinear programs (MINLP), are challenging computational problems for which new algorithmic developments are still required. These problems have two potential sources of non-convexities, the combinatorial nature of the discrete variables and the non-linear feasible region derived from the nonlinear constraints. In particular, these optimization problems have been successfully used to model applications related to Chemical Engineering. Optimal process design and operation, batch product scheduling, process superstructure optimization, and molecular design are among the areas where MINLP has been used in Chemical Engineering. For a review of these methods and their applications see [6, 8]. Among the successful approaches to tackle these problems, decomposition methods have proved to be effective. The decomposition methods rely on the solution of subproblems derived from the original optimization problem, where information can be gathered to obtain its optimal solution. The Outer-approximation (OA) method [3] is one of the most successful decomposition methods for MINLP, where an optimal solution is found by solving mixed-integer linear programming (MILP) and continuous nonlinear programming(NLP) subproblems. To guarantee the global optimality of the solution found by OA, the MILP subproblem needs to be formulated so as to provide a valid re-laxation of the original MINLP, while the NLP subproblems need to be solved to global optimality. These two conditions are satisfied when the nonlinear constraints define a convex feasible region, and the relaxation is generated from the first-order Taylor approximation of the nonlinear constraints. Problems satisfying these conditions are known as convex MINLP [5].

In this work, we propose a framework for incorporating regularization for the OA method for solving convex MINLP problems. Recently, Kronqvist et al. [4]proposed using regularization ideas for convex MINLP. Inspired by the level-based method for continuous convex problems, the authors proposed two algorithms that reduce the OA iterations and total algorithmic runtime by solving an additional regularization Mixed-integer quadratic program (MIQP) in each iteration. We pro-pose a set of functions based on norm-minimization and Lagrangian approximations as possible objective functions for the regularization auxiliary mixed-integer problem, which includes the regularization functions proposed in [4]. This approach denoted as regularization outer-approximation (ROA), which requires aMILP or MIQP subproblem solution, has been implemented as part of the open-source Mixed-integer nonlinear decomposition toolkit in Pyomo - MindtPy[1](https://pyomo.readthedocs.io/en/stable/contributed\_packages/mindtpy.html). We compare the OA method with seven regularization function alternatives for ROA. Moreover, we extend the LP/NLP Branch & Bound (B&B) method proposed by Quesada and Grossmann [7] to include regularization in an algorithm denoted RLP/NLP. We establish convergence guarantees for both ROA and RLP/NLP. Furthermore, we generalize the proof given by [4] to determine that the norm-based ROA is equivalent to adding trust-region constraints to OA. Finally, we perform significant computational experiments by considering all convex MINLP problems in the benchmark library MINLPLib[2], obtaining results illustrating the advantages of using regularization in the OA method when solving these problems. These methods become particularly well-suited for highly nonlinear instances, such as those arising in Chemical Engineering applications, allowing these problems to be solved more efficiently.

References

1. Bernal, D.E., Chen, Q., Gong, F., Grossmann, I.E.: Mixed-integer nonlinear decomposition toolbox for Pyomo (MindtPy). In: Computer Aided Chemical Engineering, vol. 44, pp. 895–900. Elsevier (2018)

2. Bussieck, M.R., Drud, A.S., Meeraus, A.: MINLPLib—a collection of test models for mixed-integer nonlinear programming. INFORMS Journal on Computing15(1), 114–119 (2003)

3. Duran, M.A., Grossmann, I.E.: An outer-approximation algorithm for a class of mixed-integer nonlinear programs. Mathematical Programming36(3), 307–339(1986)

4. Kronqvist, J., Bernal, D.E., Grossmann, I.E.: Using regularization and second-order information in outer approximation for convex MINLP. Mathematical Pro-gramming180(1), 285–310 (2020)

5. Kronqvist, J., Bernal, D.E., Lundell, A., Grossmann, I.E.: A review and comparison of solvers for convex MINLP. Optimization and Engineering20(2), 397–455(2019)

Presenter(s): 
Once the content has been viewed and you have attested to it, you will be able to download and print a certificate for PDH credits. If you have already viewed this content, please click here to login.

Checkout

Checkout

Do you already own this?

Pricing


Individuals

AIChE Member Credits 0.5
AIChE Members $19.00
AIChE Graduate Student Members Free
AIChE Undergraduate Student Members Free
Non-Members $29.00
Language: