Mixed-integer linear fractional programming (MILFP): Difference between revisions

From Cornell University Computational Optimization Open Textbook - Optimization Wiki
Jump to navigation Jump to search
Line 9: Line 9:
Consider such standard form of the MILFP:
Consider such standard form of the MILFP:


<math>\begin{align}\max {c_0+\sum_{i}c_{1i}m_i+\sum_{j}c_{2j}y_j \over d_0+\sum_{i}d_{1i}m_i+\sum_{j}d_{2j}y_j}  
\begin{align}\max {c_0+\sum_{i}c_{1,i}m_i+\sum_{j}c_{2,j}y_j \over d_0+\sum_{i}d_{1,i}m_i+\sum_{j}d_{2,j}y_j}  


\\ s.t. \quad\a_{0k}+sum_{i}a_{1i}m_i+sum_{j}a_{2j}y_j\eq 0 \quad\\
\\ s.t. \quad\a_{0,k}+sum_{i}a_{1,i}m_i+sum_{j}a_{2,j}y_j=0 \quad\\
 
        m_i &\geq 0 \quad    \end{align} </math>

Revision as of 19:48, 18 November 2020

Author: Xiang Zhao (SysEn 6800 Fall 2020)

Steward: Allen Yang, Fengqi You

Introduction

The mixed-integer linear fractional programming (MILFP) is a kind of mixed-integer nonlinear programming (MINLP) that is widely applied in chemical engineering, environmental engineering, and their hybrid field ranging from cyclic-scheduling problems to the life cycle optimization (LCO). Specifically, the objective function of the MINFP is shown as a ratio of two linear functions formed by various continuous variables and discrete variables. However, the pseudo-convexity and the combinatorial nature of the fractional objective function can cause computational challenges to the general-purpose global optimizers, such as BARON, to solve this MILFP problem. In this regard, we introduce the basic knowledge and solution steps of three algorithms, namely the Parametric Algorithm, Reformulation-Linearization method, and Branch-and-Bound with Charnes-Cooper Transformation Method, to efficiently and effectively tackle this computational challenge.

Standard Form and Properties

Consider such standard form of the MILFP:

\begin{align}\max {c_0+\sum_{i}c_{1,i}m_i+\sum_{j}c_{2,j}y_j \over d_0+\sum_{i}d_{1,i}m_i+\sum_{j}d_{2,j}y_j}

\\ s.t. \quad\a_{0,k}+sum_{i}a_{1,i}m_i+sum_{j}a_{2,j}y_j=0 \quad\\