# Mixed-integer linear fractional programming (MILFP)

uthor: 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:

{\displaystyle {\begin{aligned}\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}}\\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 ${\displaystyle \mathbb {Q} (x,y)}$ are shown as follows:

1. Numbered list item ${\displaystyle \mathbb {Q} (x,y)}$ is (strictly) pseudoconcave and pseudoconvex over its domain.
2. Numbered list item The local optimal of ${\displaystyle \mathbb {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.

## Parametric Algorithm

One way to successively reformulate and solve the MILFP is to apply the parametric algorithm, which can find the global optimality within finite iterations. The linearly parametric form of the reformulated objective function has the advantage of directly finding the global optimality, while the size of the sub-problem remains the same. The reformulation approach is shown as follows:

The original form of the objective function is: ${\displaystyle \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}}}$

We use a parametric parameter ${\displaystyle q}$ to reformulate the objective function ${\displaystyle \mathbb {Q} (x,y)}$ into ${\displaystyle \S (x,y,q)}$:

${\displaystyle \max \quad \mathbb {Q} (x,y)={A(x,y) \over B(x,y)}}$

is reformulated into

${\displaystyle \max \quad \S (x,y,q)=A(x,y)-q*B(x,y)}$

${\displaystyle A(x,y)={c_{0}+\sum _{i}c_{1,i}m_{i}+\sum _{j}c_{2,j}y_{j}}}$

${\displaystyle B(x,y)={d_{0}+\sum _{i}d_{1,i}m_{i}+\sum _{j}d_{2,j}y_{j}}}$

Notably, the optimal solution of the parametric objective function ${\displaystyle \S (x,y,q)}$ has only one zero-point, which is the same as its global optimal solution. Hence, we need to find the zero-point iteratively following the approaches below:

1. Numbered list item Initialize the parametric parameter ${\displaystyle q=0}$. Set the tolerance ${\displaystyle tol=10^{-}6}$
2. Numbered list item Solve the sub-problem via using CPLEX, whose objective function is ${\displaystyle \S (x,y,q)}$ with the same original constraints. The optimal solution is ${\displaystyle x*,y*}$.
3. Numbered list item Calculate the value of parametric objective function ${\displaystyle \S (x*,y*,q)=A(x*,y*)-q*B(x*,y*)}$, if the value is within the tolerance ${\displaystyle tol}$, then the optimality ${\displaystyle (x*,y*)}$ is found.
4. Numbered list item Update the parametric parameter ${\displaystyle q={A(x*,y*) \over B(x*,y*)}}$ and redo step 1.

## Reformulation-Linearization Method

The reformulation-linearization method, which incorporates the Glover’s linearization into the Charnes-Cooper transformation, introduce auxiliary variables to reformulate the MILFP into equivalent MINLP. The resulting MINLP is subsequently transformed into MILP, which can be efficiently solved by typical MILP solvers like CPLEX, via using Glover’s linearization.The reformulation approach is shown as follows:

The original form of the optimization model is:

{\displaystyle {\begin{aligned}\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}}\\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}}}

Firstly, we convert the fractional objective function into a bilinear constraint, as well as a substutional term ${\displaystyle g_{i}}$:

${\displaystyle u={1 \over d_{0}+\sum _{i}d_{1,i}m_{i}+\sum _{j}d_{2,j}y_{j}}}$

${\displaystyle g_{i}={m_{i}*u}}$

${\displaystyle h_{j}={y_{j}*u}}$

To get the MILP equivalent model, we use the Glover's Linearization to transform the bilinear constraint (${\displaystyle h_{j}={y_{j}*u}}$):

${\displaystyle h_{j}={y_{j}*u}}$

is equivalent to

${\displaystyle h_{j}\leq u,\quad \forall j\in J}$

${\displaystyle h_{j}\leq M*y_{j},\quad \forall j\in J}$

${\displaystyle h_{j}\geq u-M*y_{j},\quad \forall j\in J}$

${\displaystyle h_{j}\geq 0,\quad \forall j\in J}$

${\displaystyle u\geq 0,\quad \forall j\in J}$

${\displaystyle g_{i}\geq 0,\quad \forall i\in I}$

${\displaystyle h_{j}\geq 0,\quad \forall j\in J}$

${\displaystyle y_{j}\in {0,1},\quad \forall j\in J}$

In this regard, we reformulate the original MILFP model into MILP model, which can be effectively solved by typical branch-and-cut solver like CPLEX. To summarize, the reformulated MILP model is shown below:

{\displaystyle {\begin{aligned}\max \quad \mathbb {R} (u,g,h)={c_{0}*u+\sum _{i}c_{1,i}g_{i}+\sum _{j}c_{2,j}h_{j}}\\s.t.\quad \ a_{0,k}*u+\sum _{i}a_{1,i}g_{i}+\sum _{j}a_{2,j}h_{j}=0,\quad \forall k\in K\\d_{0}*u+\sum _{i}d_{1,i}g_{i}+\sum _{j}d_{2,j}h_{j}=1\\h_{j}\leq u,\quad \forall j\in J\\h_{j}\leq M*y_{j},\quad \forall j\in J\\h_{j}\geq u-M*y_{j},\quad \forall j\in J\\h_{j}\geq 0,\quad \forall j\in J\\u\geq 0,\quad \forall j\in J\\g_{i}\geq 0,\quad \forall i\in I\\h_{j}\geq 0,\quad \forall j\in J\\y_{j}\in {0,1},\quad \forall j\in J\end{aligned}}}

## Branch-and-Bound with Charnes-Cooper Transformation Method

The integration of the Charnes-Cooper transformation method into the Branch-and-Bound (B&B) algorithm can reformulate the relaxation form of the fractional objective problem in each node into an LP subproblem, which can reach its global optimality via using MILP solvers like CPLEX. Since solution steps are similar to those of B&B and the reformulation step is shown in Reformulation-Linearization Method, we encourage readers to search for B&B algorithm and paper of Gao et al.

## Application and Numerical Examples

• Applications of MILFP

Two typical applications are introduced in this section, namely cyclic scheduling and life-cycle optimization. One typical cyclic scheduling problem was illustrated in Yue et al., the fractional objective was optimized to reflect both the absolute profit and scheduling aspect, which were shown in the numerator and denominator, respectively. The combination of Reformulation-Linearization method and CPLEX were regarded as solution algorithm and the optimization framework was applied in a case study corresponding to a multiproduct batch plant that used 14 processing stages for producing three acrylic fiber formulations with a time horizon of 100 h.

In the life-cycle optimization problem of a certain processing system, the fractional objective can avoid the unreasonably maximum or minimum treatment amount from optimizing linear objective functions, and thus the balanced processing amount can be obtained to address the sustainable design and synthesis of this processing system. Notably, the functional unit is shown in the denominator, while the total economic and environmental performances are denoted as numerators in fractional objective functions. Specifically as illustrated in Gong et al., the sustainable design and synthesis of the shale gas processing system is obtained via optimizing the unit net present value (NPV), unit global warming potential (GWP), and unit freshwater consumption simultaneously. The optimization framework is applied in the Marcella Shale gas site.

In the next two numerical examples, we present a “simple form” of MILFP that can be used for selecting optimal processing pathways via maximizing unit NPV or minimizing unit GWP, respectively.

• Numerical Examples of MILFP
Figure 1. Superstructure of the chemical processing system

Let’s consider a simple chemical plant, whose superstructure is shown above. The superstructure denotes all technology options, and only one of them in each level can be chosen simultaneously. To find the optimal processing pathway on the basis of economic and environmental aspects, we consider maximizing the net present value (NPV) or minimizing unit greenhouse gas (GHG) emissions, respectively. Notably, the unit NPV equals the ratio of the NPV with the total mass flow rate of product I within ten years. The discount is 10%. The parameters are given as follows:

Conversion Rate of each Chemicals
Processing Level Conversion Rate Conversion Rate
Level 1 D to E: 0.8 D to F: 0.9
Level 2 E to G: 0.7 F to H: 0.4
Level 3 G to I: 0.5 H to I: 0.6
Fixed Capital Cost for each Technology Alternative ($) A1 A2 A3 B1 B2 B3 C1 C2 C3 12,000,000 14,000,000 15,000,000 10,000,000 12,000,000 15,000,000 22,000,000 20,000,000 21,000,000 Variable Capital Cost for each Technology Alternative ($/(ton/yr))
A1 A2 A3 B1 B2 B3 C1 C2 C3
500 400 350 600 550 450 300 350 330
Operating Cost for each Technology Alternative ($/(ton/yr)) A1 A2 A3 B1 B2 B3 C1 C2 C3 250 300 200 300 280 500 270 250 150 Feedstock Supply and Demand of Product (ton/yr)/Feedstock and Product Price ($/(ton/yr))
Item Supply/Demand Feedstock/Product Price
D 2,000,000 100
I 200,000 600
GHG Emissions from each Technology Option (ton CO2-eq/ton inlet chemicals)
A1 A2 A3 B1 B2 B3 C1 C2 C3
1.2 0.9 0.7 1.4 1.6 1.3 2.1 2.4 2.7