Mixed-integer linear fractional programming (MILFP)

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:

$\max \quad \mathbb {Q} (x,y)={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}}$

${\begin{aligned}s.t.\quad \ a_{0,k}+\sum _{i}a_{1,i}m_{i}+\sum _{j}a_{2,j}y_{j}=0,\quad \forall k\in K\\m_{i}\geq 0,\quad \forall i\in I\\y_{j}\in {0,1},\quad \forall j\in J\end{aligned}}$

The properties of the objective function Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Q(x,y)} are shown as follows:

1. Numbered list item Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Q(x,y)} is (strictly) pseudoconcave and pseudoconvex over its domain.
2. Numbered list item The local optimal of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Q(x,y)} is the same as its global optimal.

Notably, several nonlinear solvers that can deal with the pseudoconvexity, such as the spatial branch-and-bound (SBB), are capable of solving the MILFP. However, the memory usage of these solvers is enormous when solving a large-scale problem that is applied in industrial scheduling or supply chain optimization project. Hence, we introduce the parametric algorithm, and reformulation-linearization method, which can reformulate the MILFP into the mixed-integer linear programming (MILP) problem, to reduce the memory usage and enhance solution efficiency.