A trajectory-based method for mixed integer nonlinear programming problems.

*(English)*Zbl 1393.90075Summary: A local trajectory-based method for solving mixed integer nonlinear programming problems is proposed. The method is based on the trajectory-based method for continuous optimization problems. The method has three phases, each of which performs continuous minimizations via the solution of systems of differential equations. A number of novel contributions, such as an adaptive step size strategy for numerical integration and a strategy for updating the penalty parameter, are introduced. We have shown that the optimal value obtained by the proposed method is at least as good as the minimizer predicted by a recent definition of a mixed integer local minimizer. Computational results are presented, showing the effectiveness of the method.

##### MSC:

90C11 | Mixed integer programming |

##### Keywords:

trajectory-based method; mixed integer nonlinear programming; system of ordinary differential equations; neighborhood; local minimizer; subproblem; pattern search
PDF
BibTeX
XML
Cite

\textit{T.-L. Oliphant} and \textit{M. M. Ali}, J. Glob. Optim. 70, No. 3, 601--623 (2018; Zbl 1393.90075)

Full Text:
DOI

##### References:

[1] | Cornuejols, G., Tutuncu, R.: Optimization Methods in Finance. Cambridge University Press, Cambridge (2007) · Zbl 1117.91031 |

[2] | Housh, M; Ostfels, A; Shamir, U, Box-constrained optimization methodology and its application for a water supply system model, J. Water Resour. Plan. Manag., 138, 651-659, (2012) |

[3] | Bartholomew Biggs, M.: Nonlinear optimization and engineering applications. Springer optimization and its applications (2008) · Zbl 1167.90001 |

[4] | Ryberg, A., Backryd, R.D., Nilsson, L.: Metamodel-based multidisciplinary design optimization for automotive applications. Technical Report, Division of solid mechanics, Linkoping University (Institute of technology), Linkoping (2012) |

[5] | Dakin, RJ, A tree-search algorithm for mixed integer programming problems, Comput. J., 8, 250-255, (1965) · Zbl 0154.42004 |

[6] | Ryoo, HS; Sahinidis, NV, Global optimization of non-convex NLPs and MINLPs with applications in process design, Comput. Chem. Eng., 19, 551-566, (1995) |

[7] | Leyffer, S, Integrating SQP and branch-and-bound for mixed integer nonlinear programming, Comput. Optim. Appl., 18, 295-309, (2001) · Zbl 1009.90074 |

[8] | Adjiman, CS; Androulakis, IP; Floudas, CA, Global optimization of mixed integer nonlinear problems, AIChE J., 46, 1769-1797, (2000) |

[9] | Duran, MA; Grossman, IE, An outer-approximation algorithm for a class of mixed-integer nonlinear programs, Math. Program., 36, 307-339, (1986) · Zbl 0619.90052 |

[10] | Fletcher, R; Leyffer, S, Solving mixed integer nonlinear programs by outer approximation, Math. Program., 66, 327-349, (1994) · Zbl 0833.90088 |

[11] | Westerlund, T; Pettersson, F, An extended cutting plane method for solving convex MINLP problems, Comput. Chem. Eng., 19, 131-136, (1995) |

[12] | Pörn, R; Westerlund, T, A cutting plane method for minimizing pseudo-convex functions in the mixed integer case, Comput. Chem. Eng., 24, 2655-2665, (2000) |

[13] | Abhisek, K; Leyffer, S; Linderoth, J, An outer approximation-based solver for convex mixed-integer nonlinear programs, INFORMS J. Comput., 22, 555-567, (2010) · Zbl 1243.90142 |

[14] | Naoum-Saqaya, J; Elhedhlic, S, An interior point cutting plane heuristic method for mixed integer programming, Comput. Oper. Res., 38, 1335-1341, (2011) · Zbl 1208.90121 |

[15] | Lucidi, S; Rinaldi, F, An exact penalty global optimization approach for mixed integer programming problems, Optim. Lett., 7, 375-405, (2013) · Zbl 1288.90054 |

[16] | Newby, E; Ali, MM, A note on convex reformulation schemes for mixed integer quadratic programs, J. Optim. Theory Appl., 160, 457-469, (2014) · Zbl 1298.90060 |

[17] | Newby, E; Ali, AA, Transformation-based preprocessing for mixed-integer quadratic programs, J. Optim. Theory Appl., 168, 1039-1045, (2016) · Zbl 1338.90276 |

[18] | Newby, E; Ali, M,M, Linear transformation based solution methods for non-convex mixed integer quadratic programs, Optim. Lett., 11, 967-981, (2017) · Zbl 1373.90084 |

[19] | Snyman, JA, A new dynamic method for unconstrained minimization, Appl. Math. Modelling, 6, 449-462, (1982) · Zbl 0501.65026 |

[20] | Snyman, JA, An improved version of the original leap-frog dynamic method for unconstrained minimization LFOP1(b), Appl. Math. Modelling, 7, 216-218, (1983) · Zbl 0548.65046 |

[21] | Newby, E; Ali, MM, A trust-region-based derivative free algorithm for mixed integer programming, Comput. Optim. Appl., 60, 1-31, (2014) |

[22] | Nocedal, J., Wright, S.J.: Numerical Optimization. Springer, New York (1999) · Zbl 0930.65067 |

[23] | Oliphant, T.N.B.: Trajectory-based methods for solving nonlinear and mixed integer nonlinear programming problems. Ph.D. dissertation, University of the Witwatersrand (2015) |

[24] | Butcher, JC, Optimal order and step size sequences, IMA J. Numer. Anal., 6, 433-438, (1986) · Zbl 0615.65076 |

[25] | Birgin, E.G., Fernandez, D., Martinez, J.M.: On the boundedness of penalty parameters in an augmented Lagrangian method with lower level constraints. Technical Report, Department of Applied Mathematics, State University of Campinas, Brazil · Zbl 1247.90247 |

[26] | Birgin, EG; Martinez, JM, Augmented Lagrangian method with non-monotone penalty parameters for constrained optimization, Comput. Optim. Appl., 51, 941-965, (2012) · Zbl 1244.90216 |

[27] | Kolda, TG; Lewis, RM; Torczon, V, Optimization by direct search: new perspectives on some classical and modern methods, SIAM Rev., 45, 385-482, (2003) · Zbl 1059.90146 |

[28] | Ali, M.M., Oliphant, T.N.B.: A trajectory-based method for constrained nonlinear optimization problems, under revision (2017) · Zbl 1009.90074 |

[29] | Pörn, R; Harjunkoski, I; Westerlund, T, Convexification of different classes of non-convex MINLP problems, Comput. Chem. Eng., 23, 439-448, (1999) |

[30] | Kocis, GR; Grossmann, IE, Global optimization of nonconvex mixed-integer nonlinear programming (MINLP) problems in process synthesis, Ind. Eng. Chem. Res., 27, 1407-1421, (1998) |

[31] | Harjunkoski, I.: Application of MINLP methods to a scheduling problem in the paper-converting industry. Ph.D. dissertation, Process Design Laboratory, Department of Chemical Engineering, Abo Akademi University (1997) · Zbl 1035.90051 |

[32] | Emet, S.: A comparative study of solving some non-convex MINLP problems. Ph.D. dissertation, Abo Akademi University (2004) |

[33] | Westerlund, T; Pörn, R, Solving pseudo-convex mixed integer optimization problems by cutting plane techniques, Optim. Eng., 3, 253-280, (2002) · Zbl 1035.90051 |

[34] | Pörn, R.: Mixed integer non-linear programming: convexification techniques and algorithm development. Ph.D. dissertation, Abo Akademi University (2000) |

[35] | Floudas, C.A.: Nonlinear and Mixed-Integer Optimization: Fundamentals and Applications. Oxford University Press, Oxford (1995) · Zbl 0886.90106 |

[36] | Cardoso, M.F., Salcedo, R.L., Feyo de Azevedo, S., Barbosa, D.: A simulated annealing approach to the solution of MINLP problems. Comput. Chem. Eng. 21, 1349-1364 (1997) |

[37] | Nzengang, F.V: Introduction to mixed integer nonlinear programming. M.Sc. dissertation, African Institute for Mathematical Sciences (2010) |

[38] | Quesada, I; Grossmann, IE, A global optimization algorithm for linear fractional and bilinear programs, J. Glob. Optim., 6, 39-76, (1995) · Zbl 0835.90074 |

[39] | Polisetty, P.K., Gatzke, E.P.: A decomposition-based MINLP solution method using piecewise linear relaxations. Int. Trans. Oper. Res. (2005) · Zbl 1373.90084 |

[40] | Floudas, C.A., Pardalos, P.M., Adjiman, C., Esposito, W.R., Gümüs, Z.H., Harding, S.T., Klepeis, J.L., Meyer, C.A., Schweiger, C.A.: Handbook of Test Problems in Local and Global Optimization. Springer, Berlin (2013) · Zbl 0943.90001 |

[41] | Kocis, GR; Grossmann, IE, A modelling and decomposition strategy for the MINLP optimization of process flowsheets, Comput. Chem. Eng., 13, 797-819, (1989) |

[42] | Adjiman, CS; Androulakis, IP; Floudas, CA, Global optimization of MINLP problems in process synthesis and design, Comput. Chem. Eng., 21, s445-s450, (1997) |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.