View source for 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,<sup>[https://aiche.onlinelibrary.wiley.com/doi/full/10.1002/btpr.2479]</sup> environmental engineering,<sup>[http://ourspace.uregina.ca/handle/10294/5449]</sup> and their hybrid field ranging from cyclic-scheduling problems to the life cycle optimization (LCO).<sup>[https://pubs.acs.org/doi/abs/10.1021/acssuschemeng.7b00002?casa_token=hJNBUOc-zyIAAAAA:8gqZM144_Hjovhq_fLHXRQT66FGp0tf6oZ3rWiuRJLD4YKp4f1S44UkUspsNZuCCrcCFIWYME1v0dGPYLA]</sup> 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 [[wikipedia:BARON|BARON]], to solve this MILFP problem.<sup>[https://www.sciencedirect.com/science/article/pii/S0098135413003396?casa_token=Y6pefF84TQAAAAAA:ALrnGQIOGXr3SA-oqbD3FmlFsMyjp_z4zgmY8LkWscSWtbO8pMjFGix35FsroEVxI9ut0mWjffZc]</sup> 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:

<math>\begin{align}\max \quad\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\ge0,\quad \forall i \in I\\
       
       y_j\in {0,1},\quad \forall j \in J \end{align}</math>

The properties of the objective function <math>\Q(x,y)</math> are shown as follows:<sup>[https://www.sciencedirect.com/science/article/pii/S0098135409001367?casa_token=Sj60B1tEjccAAAAA:kMeO3BLDWNBd7jkBDqcpR5nTrB3yryQ8_CNqyN1mMooiuZxSiLfoVwtkDuU3cTWu4e0FsmeWN_uw]</sup> 
# <math>\Q(x,y)</math> is (strictly) pseudoconcave and pseudoconvex over its domain.
# The local optimality of <math>\Q(x,y)</math> is the same as its global optimality.

Notably, several nonlinear solvers that can deal with the pseudoconvexity, such as the spatial branch-and-bound (SBB),<sup>[https://link.springer.com/article/10.1007/BF01106605]</sup> 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 [[wikipedia:supply chain|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 [[wikipedia:parametric form|parametric form]] of the reformulated objective function has the advantage of directly finding the [[wikipedia:global optimum|global optimum]], 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:
<math>\quad\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}</math>

We use a parametric parameter <math>q</math> to reformulate the objective function <math>\Q(x,y)</math> into <math>\S(x,y,q)</math>:

<math>\max \quad\Q(x,y)={A(x,y) \over B(x,y)}</math>

is reformulated into 

<math>\max \quad\S(x,y,q)=A(x,y)-q*B(x,y)</math>

<math>A(x,y)={c_0+\sum_{i}c_{1,i}m_i+\sum_{j}c_{2,j}y_j}</math>

<math>B(x,y)={d_0+\sum_{i}d_{1,i}m_i+\sum_{j}d_{2,j}y_j}</math>

Notably, the optimal solution of the parametric objective function <math>\S(x,y,q)</math> 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:<sup>[https://ieeexplore.ieee.org/abstract/document/6858622?casa_token=jvj28BEMe0cAAAAA:utpZe4zST7nz0SVcdNUoX-CjmqmtU_v3CZnU-oTAxvR8B7ZV2iBjyhqDy3s-228w7Aw4_lcJjFw]</sup>

# Initialize the parametric parameter <math>q=0</math>. Set the tolerance <math>tol=10^{-6}</math>  
# Solve the sub-problem via using [[wikipedia:CPLEX|CPLEX]], whose objective function is <math>\S(x,y,q)</math> with the same original constraints. The optimal solution is <math>x*,y*</math>. 
# Calculate the value of parametric objective function <math>\S(x*,y*,q)=A(x*,y*)-q*B(x*,y*)</math>, if the value is within the tolerance <math>tol</math>, then the optimality <math>(x*,y*)</math> is found.
# Update the parametric parameter <math>q={A(x*,y*) \over B(x*,y*)}</math> and redo step 1.

==Reformulation-Linearization Method==
The reformulation-linearization method, which incorporates the Glover’s linearization<sup>[https://glossary.informs.org/ver2/mpgwiki/index.php/Glovers_linearization]</sup> into the Charnes-Cooper transformation,<sup>[https://onlinelibrary.wiley.com/doi/abs/10.1002/nav.3800200308?casa_token=BsaOkI0dilIAAAAA:wPELPH83o1FuB9xHW8rRDhwInT3xsGjqqqk6LWID7WYpLexkAhgiymU-4-ew7c0nEoC3wM49-oFHa1m5]</sup> 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 [[wikipedia:CPLEX|CPLEX]], via using Glover’s linearization.The reformulation approach is shown as follows:

The original form of the optimization model is:

<math>\begin{align}\max \quad\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\ge0,\quad \forall i \in I\\
       
       y_j\in {0,1},\quad \forall j \in J \end{align}</math>

Firstly, we convert the fractional objective function into a bilinear constraint, as well as a substutional term <math>g_i</math>:

<math>u={1\over d_0+\sum_{i}d_{1,i}m_i+\sum_{j}d_{2,j}y_j}</math>

<math>g_i={m_i*u}</math>

<math>h_j={y_j*u}</math>

To get the MILP equivalent model, we use the Glover's Linearization to transform the bilinear constraint (<math>h_j={y_j*u}</math>):

<math>h_j={y_j*u}</math>

is equivalent to

<math>h_j\leq u,\quad \forall j \in J</math>

<math>h_j\leq M*y_j,\quad \forall j \in J</math>

<math>h_j\geq u-M*y_j,\quad \forall j \in J</math>

<math>h_j\geq 0,\quad \forall j \in J</math>

<math>u\geq 0,\quad \forall j \in J</math>

<math>g_i\geq 0,\quad \forall i \in I</math>

<math>h_j\geq 0,\quad \forall j \in J</math>

<math>y_j\in {0,1},\quad \forall j \in J</math>

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

<math>\begin{align}\max \quad\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{align}</math>

==Branch-and-Bound with Charnes-Cooper Transformation Method==
The integration of the Charnes-Cooper transformation method with the [[wikipedia:Branch and Bound|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 [[wikipedia:CPLEX|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.<sup>[https://aiche.onlinelibrary.wiley.com/doi/full/10.1002/aic.14705]</sup>

==Application and Modeling for Numerical Examples==

=== Applications of MILFP ===

Two typical applications are introduced in this section, namely [[wikipedia:cyclic scheduling|cyclic scheduling]] and [[wikipedia:life-cycle optimization|life-cycle optimization]]. One typical cyclic scheduling problem was illustrated in Yue et al.<sup>[https://www.sciencedirect.com/science/article/pii/S0098135413000781]</sup>, 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 [[wikipedia:CPLEX|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 unreasonably maximum or minimum treatment amount from optimizing linear objective functions can be avoided via optimizing the fractional objective, and thus the balanced processing amount can be obtained to address the sustainable design and synthesis of this processing system.<sup>[https://pubs.acs.org/doi/abs/10.1021/acssuschemeng.7b03198?casa_token=dokyfl7kzigAAAAA:Z6riBbyfYZgakqA0Qw6du37ClfOFBuBKQxcuExnuWUvniwFWEjx17ivfLo4uvTgsl4eMBukRxfLYXW6dsA]</sup> 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.,<sup>[https://aiche.onlinelibrary.wiley.com/doi/full/10.1002/aic.15882]</sup> the sustainable design and synthesis of the shale gas processing system was obtained via optimizing the unit net present value (NPV), unit global warming potential (GWP), and unit freshwater consumption simultaneously. The optimization framework was 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 ===

==== Introduction of Numerical Examples ====

[[File:Opti wiki.jpg|thumb|right|Figure 1. Superstructure of the chemical processing system]]
Let’s consider a simple chemical plant, whose superstructure is shown on the right side. 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 the project lifespan of ten years. The discount rate is 10%.

==== Input Parameters of Numerical Examples ====

{| class="wikitable"
|+ Conversion Rate of each Chemicals
|-
! Processing Level !! Conversion Rate !! Conversion Rate !! Conversion Rate
|-
| Level 1 || D to E: 0.8 || D to F: 0.9
|-
| Level 2 || E to G: 0.7 || E to H: 0.8 || F to H: 0.4
|-
| Level 3 || G to I: 0.5 || H to I: 0.6
|}

{| class="wikitable"
|+ Fixed Capital Cost for each Technology Alternative ($)
|-
! A1 !! A2 !! A3 !! B1 !! B2 !! B3 !! C1 !! C2 !! C3
|-
| 6,000,000 || 7,000,000 || 7,500,000 || 5,000,000 || 6,000,000 || 7,500,000 || 11,000,000 || 10,000,000 || 10,500,000
|}

{| class="wikitable"
|+ Variable Capital Cost for each Technology Alternative ($/(ton/yr))
|-
! A1 !! A2 !! A3 !! B1 !! B2 !! B3 !! C1 !! C2 !! C3
|-
| 50 || 40 || 35 || 60 || 55 || 45 || 30 || 35 || 33
|}

{| class="wikitable"
|+ Operating Cost for each Technology Alternative ($/(ton/yr))
|-
! A1 !! A2 !! A3 !! B1 !! B2 !! B3 !! C1 !! C2 !! C3
|-
| 25 || 30 || 20 || 30 || 28 || 50 || 27 || 25 || 15
|}

{| class="wikitable"
|+ 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  || 2000
|}

{| class="wikitable"
|+ GHG Emissions from each Technology Option (ton CO<sub>2</sub>-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
|}

==== Nomenclatures for the Mathematical Model of the Numerical Examples ====

{| class="wikitable"
|+ Nomenclature
|-
! Nomenclature !! Meaning
|-
| ''I'' || Set of production stages indexed by ''i''.
|-
| ''J'' || Set of process alternatives ''j''.
|-
| ''D'' || Demand of product I.
|-
| ''CAV<sub>i,j</sub>'' || Unit variable capital cost in the process alternative ''j'' at the production stage ''i''.
|-
| ''CV<sub>i,j</sub>'' || Conversion rate from input flow to output flow in the process alternative ''j'' at the production stage ''i''. 
|-
| ''FIXI<sub>i,j</sub>'' || Fixed capital cost in the process alternative ''j'' at the production stage ''i''.
|-
| ''GHG<sub>i,j</sub>'' || Unit GHG emissions from the process alternative ''j'' at the production stage ''i''.
|-
| ''OPERI<sub>i,j</sub>'' || Unit operating cost in the process alternative ''j'' at the production stage ''i''.
|-
| ''PRI'' || Price of product I.
|-
| ''PRID'' || Price of chemical D.
|-
| ''S'' || Supply of chemical D.
|-
| ''y<sub>i,j</sub>'' || 0-1 variable. Equal to one if the process alternative ''j'' at the production stage ''i'' is selected. 
|-
| ''ca<sub>i,j</sub>'' || Capacity of process alternative ''j'' at the production stage ''i''. 
|-
| ''fec'' || Total feedstock cost. 
|-
| ''fix'' || Total fixed capital cost. 
|-
| ''ghgt'' || Total GHG emissions.
|-
| ''mi<sub>i,j</sub>'' || Mass flow rate of the feedstock flow to process alternative ''j'' at the production stage ''i''.
|-
| ''mo<sub>i,j</sub>'' || Mass flow rate of the output flow to the process alternative ''j'' at the production stage ''i''.
|-
| ''oper'' || Total operating cost. 
|-
| ''objc'' || Unit net present value (NPV).
|-
| ''obje'' || Unit GHG emissions (within one operating year).
|-
| ''npv'' || Net present value.
|-
| ''sale'' || Total sales.
|-
| ''vai'' || Total variable capital cost. 
|}


===== Mass Balance Constraints =====

  <math>mi_{i,j} \leq ca_{i,j},\quad \forall i \in I,\forall j \in J</math>

This aforementioned constraint denotes that the mass flow rate of the inlet flow should not exceed the treatment capacity.

  <math>ca_{i,j} \leq M*y_{i,j},\quad \forall i \in I,\forall j \in J</math>

This aforementioned constraint represents that the treatment capacity would be zero if the corresponding technology option is not selected.

  <math>mo_{i,j} = mi_{i,j}*CV_{i,j},\quad \forall i \in I,\forall j \in J</math>

This aforementioned constraint illustrates the conversion of the inlet flow and the outlet flow.

  <math>\sum_{j}mo_{i-1,j} = \sum_{j}mi_{i,j},\quad \forall i \geq 2,\forall j \in J</math>

This aforementioned constraint denotes that the summation of mass flow rates of the outlet flows from the previous processing level equals to those of the inlet flows in the next processing level.

  <math>\sum_{j}mo_{3,j} \geq D,\quad \forall i \in I,\forall j \in J</math>

This aforementioned constraint represents that the summation of mass flow rates of the technology options in the third processing level should be larger than the demand of the product I.

  <math>\sum_{j}mi_{1,j} \leq S,\quad \forall i \in I,\forall j \in J</math>

This aforementioned constraint represents that the summation of mass flow rates of the technology options in the first processing level should be less than the supply of the chemical D.

===== Superstructure Configuration Constraints =====

Notably, the superstructure configuration constraints illustrate the logic relationship between each technology option within the superstructure. If the binary variable <math>y_{i,j}</math> equals to 1, than the technology option <math>j</math> in the process level <math>i</math> is selected.

  <math>y_{1,1}+y_{1,2}+y_{1,3} = 1</math>

  <math>y_{1,1}+y_{1,2}=y_{2,1}+y_{2,2}</math>

  <math>y_{1,3}=y_{2,3}</math>

  <math>y_{2,1}=y_{3,1}</math>

  <math>y_{2,2}+y_{2,3}=y_{3,2}+y_{3,3}</math>

===== Economic Evaluation Constraints =====

We consider the fixed capital cost (<math>fix</math>), variable capital cost (<math>vai</math>), operating cost (<math>oper</math>), and feedstock cost (<math>fec</math>) as the expenses for the chemical processing system. 

  <math>fix=\sum_{i}{\sum_{j}FIXI_{i,j}*y_{i,j}}</math>

  <math>vai=\sum_{i}{\sum_{j}CAV_{i,j}*ca_{i,j}}</math>

  <math>oper=\sum_{i}{\sum_{j}OPERI_{i,j}*mo_{i,j}}</math>

  <math>fec=PRID*\sum_{j}mi_{1,j}</math>

  <math>sale=PRI*\sum_{j}mo_{3,j}</math>

The net present value is calculated in the constraint below (<math>fix</math>), where we account for the total discounted cash flow (<math>{DR*(1+DR)^{SP} \over (1+DR)^{SP}-1}*(sale-vai-oper-fec)</math>) and <math>SP</math> represents for the lifespan of the this project. 

  <math>npv={DR*(1+DR)^{SP} \over (1+DR)^{SP}-1}*(sale-vai-oper-fec)-fix</math>

===== Environmental Evaluation Constraint =====

The total GHG emissions from the chemical processing system is calculated in the constraint below.
  <math>ghgt=\sum_{i}{\sum_{j}GHG_{i,j}*mi_{i,j}}</math>

===== Objective Functions =====

Two numerical examples are presented as optimizing each fractional objective functions, which are shown as below. Since all constraints denote the relationship between various continous and discrete variables, two aforementioned numerical problems can be regarded as MILFPs. We consider maximizing unit NPV (<math>\max \quad\ obje</math>) or minimizing unit GWP (<math>\min \quad\ ghgt</math>) in two numerical examples, respectively. 

  <math>obje={npv \over \sum_{j}mo_{3,j}}</math>

  <math>objc={ghgt \over \sum_{j}mo_{3,j}}</math>

==Solution for Numerical Examples==

===Maximizing Unit NPV===

We consider the first objective function (<math>obje</math>) and all constraints in the mathematical model, where we can reformulate the objective function into a parametric form (<math>obj_1</math>) using parametric parameter <math>q_1</math>:

  <math>\max \quad\ obj_1={npv-q_1*\sum_{j}mo_{3,j}}</math>

  <math>s.t.\quad\ Mass \ \ Balance\ \ Constraints, Superstructure\ \ Configuration\ \ Constraints, Economic\ \ Evaluation\ \ Constraints</math>

This reformulated model can be solved by the [[wikipedia:CPLEX|CPLEX]] iteratively, and the solution is shown as follows:
{| class="wikitable"
|+ Process to be built
|-
! Level 1 !! Level 2 !! Level 3
|-
| A1 || - || -
|-
| - || B2 || -
|-
| - || - || C3
|}

{| class="wikitable"
|+ Performance
|-
! Production Amount (ton/yr) !! Unit NPV ($/ton) !! Unit GHG Emissions (ton CO<sub>2</sub>-eq/ton products)
|-
| 768,000 || 187.75 || 10.18
|}

===Minimizing Unit GHG Emissions===

We consider the first objective function (<math>objc</math>) and all constraints in the mathematical model, where we can reformulate the objective function into a parametric form (<math>obj_2</math>) using parametric parameter <math>q_2</math>:

  <math>\min \quad\ obj_2={ghgt-q_2*\sum_{j}mo_{3,j}}</math>

  <math>s.t.\quad\ Mass\ \ Balance\ \ Constraints, Superstructure\ \ Configuration\ \ Constraints, Environmental\ \ Evaluation\ \ Constraints</math>

This reformulated model can be solved by the [[wikipedia:CPLEX|CPLEX]] iteratively, and the solution is shown as follows:
{| class="wikitable"
|+ Process to be built
|-
! Level 1 !! Level 2 !! Level 3
|-
| - || - || -
|-
| A2 || B2 || C2
|-
| - || - || -
|}

{| class="wikitable"
|+ Performance
|-
! Production Amount (ton/yr) !! Unit NPV ($/ton) !! Unit GHG Emissions (ton CO<sub>2</sub>-eq/ton products)
|-
| 768,000 || 186.23 || 9.68
|}

==References==