(482b) Tailored Global Optimization Algorithms for Mixed-Integer Linear Fractional Programming Problems

Mixed-integer linear fractional programming (MILFP) is a class of mixed-integer nonlinear program (MINLP) [1]. It is such a problem that includes both continuous and discrete variables and seeks to optimize an objective function formulated as a ratio of two linear functions subject to linear constraints. MILFP models usually occur in the planning and scheduling optimization for production process or when we apply the concept of functional unit as in the life-cycle assessment (LCA) [2-4]. MILFPs can be computationally intractable for large-scale problems due to its combinatorial nature and pseudo-convexity. In this work, we propose three tailored algorithms to solve this MILFP problem and compare their computation performance.

Normally, MILFPs can be solved by general Mixed-Integer Nonlinear Programming (MINLP) solvers as SBB, DICOPT and BARON [5]. However, for large-scale MILFP problem these general MINLP solvers may be unable to efficiently solve for optimal solution. Based on this situation, we present three tailored algorithms, including the parametric algorithm, reformulation-linearization algorithm and Charnes-Cooper + Branch & Bound algorithm.

Parametric algorithm, which transforms the original MILFP problem to a set of equivalent Mixed-Integer Linear Programming (MILP) subproblems, is proven to be an efficient method for solving MILFP problem [4, 6]. The advantage of parametric algorithm is that the size of each subproblem doesn’t change; however the literation times are unpredictable and no gap information will be returned during solution.

Another one is the reformulation-linearization method, which combines the Charnes-Cooper transformation and Glove’s linearization method together to transform the original MILFP problem to an equivalent MILP problem by introducing extra auxiliary variables and constraints [7]. The main advantage of reformulation-linearization algorithms is that the equivalent MILP problem only needs to be solved once to get the exact optimal solution for the original problem, and the gap information is available during solution. The drawback is the problem size increases due to the introduction of new variables and constraints.

The last one is Charnes-Cooper + Branch and Bound algorithm, in which we combine the Charnes-Cooper transformation and the branch-and-bound algorithm together [8]. By applying Charnes-Cooper transformation, we get rid of the fractional form of the original objective function. Moreover, we replace the bilinear terms result from Charnes-Cooper transformation with newly introduced variables. By using branch-and-bound algorithm, we guarantee the discrete nature of original binary variables implicitly included in the newly introduced variables. By integrating these two steps, we are able to transform the original MILFP problem into a set of Linear Programming (LP) subproblems, which can be efficiently solved by any LP solver, such as CPLEX. Obviously for each LP subproblem, it’s much easier to solve than an MILP, however, due to the nature of branch-and-bound, the actual performance of this algorithm highly rely on the node selecting strategy.   

The computation performance for these three solution approaches is demonstrated by some random generated examples and a large-scale MILFP problem derived from an optimal design and operation of water supply chain problem. The results are also compared with those returned by the MINLP solvers, SBB, DICOPT and BARON 12. According to the results, for most cases, parametric algorithm is times faster than other approaches; reformulation-linearization is normally slower but comparable to parametric algorithm; Charnes-Cooper transformation and Branch & Bound, though slower than parametric algorithm and reformulation-linearization, is faster than SBB, and BARON 12. In conclusion, all these three presented algorithms showed their efficiency in in solving large-scale MILFP problems, and parametric algorithm is the most extraordinary one.

References

[1]        C. A. Floudas, Deterministic global optimizationvol. 37: Springer, 2000.

[2]        D. Yue, F. You, and S. W. Snyder, "Biomass-to-bioenergy and biofuel supply chain optimization: Overview, key issues and challenges," Computers & Chemical Engineering, 2013.

[3]        Y. Chu and F. You, "Integration of production scheduling and dynamic optimization for multi-product CSTRs: Generalized Benders decomposition coupled with global mixed-integer fractional programming," Computers & Chemical Engineering, vol. 58, pp. 315-333, 11/11/ 2013.

[4]        Z. X. Zhong and F. Q. You, "Globally convergent exact and inexact parametric algorithms for solving large-scale mixed-integer fractional programs and applications in process systems engineering," Computers & Chemical Engineering, vol. 61, pp. 90-101, Feb 2014.

[5]        M. Tawarmalani and N. V. Sahinidis, "A polyhedral branch-and-cut approach to global optimization," Mathematical Programming, vol. 103, pp. 225-249, 2005/06/01 2005.

[6]        F. 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 and Chemical Engineering, vol. 33, pp. 1879-1889, 2009.

[7]        D. Yue, G. Guillén‐Gosálbez, and F. You, "Global optimization of large‐scale mixed‐integer linear fractional programming problems: A reformulation‐linearization method and process scheduling applications," AIChE Journal, vol. 59, pp. 4255-4272, 2013.

[8]        A. Charnes and W. W. Cooper, "Programming with linear fractional functionals," Naval Research Logistics Quarterly, vol. 9, pp. 181-186, 1962.