(398d) A Parametric Approach for the Global Optimization of Mixed-Integer Fractional Programs

Mixed-integer fractional programming (MIFP) problems frequently occur in process engineering, e.g. cyclic scheduling [1], and integration scheduling and control [2, 3]. In this work, we specifically consider the MIFPs with a convex quadratic function in the numerator and a linear function in the denominator. This is a non-convex mixed integer nonlinear programming (MINLP) problem and we developed an efficient approach for its global optimization.

First, the relaxed MIFP problem is proved to be quasi-convex. Based on the property, the MINLP solver SBB [4] can guarantee the global optimality. Because each nonlinear programming (NLP) subproblem in the branch-and-bound is solved to the global optimum, the global solution to the MINLP problem can be obtained by a standard branch-and-bound algorithm. Another popular MINLP solver DICOPT [5] uses the outer-approximation method and it might cut off some feasible solution space during the iterations. Thus, DICOPT cannot guarantee the global optimality of the solution. The global optimal solution can be also obtained by the global MINLP solvers, such as BARON [6] and GloMIQO [7].

Second, the MIFP is transformed into an equivalent parametric mixed-integer programming (PMIP) problem which is the numerator minus the denominator multiplied by a parameter. The solution to the PMIP problem is a function of the parameter, called the optimal value function. A feasible solution to the MIFP problem is the global optimal solution if and only if the solution is also the global optimal solution to the PMIP problem with the parameter which is the root of the optimal value function [8-10]. The condition for the equivalence is very general, i.e. the denominator should be positive. There are no assumptions required on the types or the convexities of the functions in the numerator and the denominators. However, the equivalence is true only for the global minima of the two problems. For the problem we consider, the equivalent PMIP problem is a convex mixed-integer quadratic programming (MIQCQ) problem and it can be solved to the global minimum by state-of-the-art solvers, such as CPLEX, in an efficient way. To guarantee the equivalence, the PMIP problem must be solved at the parameter which is the root of the optimal value function.

Third, two approaches are applied to find the root of the optimal value function which has no explicit expression. They are the bisection method [8] and the generalized Newton’s method [10]. The bisection method only uses the sign information of F(q) in the iteration while the generalized Newton’s method requires the information of the subgradient. By using more information of the function, the generalized Newton’s method has a faster convergence rate than the bisection method. The Newton's method converges supper-linearly while the bisection algorithm converges linearly.

The PMIP solution approaches based on the bisection method and the Newton’s method are demonstrated by a large-scale MIFP problem derived from an integrated scheduling and control problem [3]. The results are compared with those returned by the MINLP solvers, SBB, DICOPT, and BARON 9.3.1. The results showed that the proposed approaches can globally optimize the MIFPs within much shorter times than general-purpose MINLP methods.

References

[1]          J. M. Pinto and I. E. Grossmann, "Optimal cyclic scheduling of multistage continuous multiproduct plants," Computers & Chemical Engineering, vol. 18, pp. 797-816, 1994.

[2]        A. Flores-Tlacuahuac and I. E. Grossmann, "Simultaneous cyclic scheduling and control of a multiproduct CSTR," Industrial & Engineering Chemistry Research, vol. 45, pp. 6698-6712, 2006.

[3]        Y. Chu and F. You, "Integration of scheduling and control with online closed-loop implementation: Fast computational strategy and large-scale global optimization algorithm," submitted to Computers & Chemical Engineering, 2012.

[4]        M. R. Bussieck and A. S. Drud. SBB: A new solver for mixed integer nonlinear programming [Online]. Available: http://www.gams.com/presentations/or01/sbb.pdf

[5]        G. R. Kocis and I. E. Grossmann, "Computational experience with DICOPT solving MINLP problems in process systems engineering," Computers & Chemical Engineering, vol. 13, pp. 307-315, 1989.

[6]        M. Tawarmalani and N. V. Sahinidis, "Global optimization of mixed-integer nonlinear programs: A theoretical and computational study," Mathematical Programming, vol. 99, pp. 563-591, 2004.

[7]        R. Misener and C. A. Floudas, "GloMIQO: Global mixed-integer quadratic optimizer.," Journal of Global Optimization, in press, 2012.

[8]        J. R. Bradley and B. C. Arntzen, "The simultaneous planning of production, capacity, and inventory in seasonal demand environments," Operations Research, vol. 47, pp. 795-806, 1999.

[9]        W. Dinkelbach, "On Nonlinear Fractional Programming," Management Science, vol. 13, pp. 492-498, 1967.

[10]      F. Q. You, P. M. Castro, and I. E. Grossmann, "Dinkelbach's algorithm as an efficient method to solve a class of MINLP models for large-scale cyclic scheduling problems," Computers & Chemical Engineering, vol. 33, pp. 1879-1889, 2009.