Mixed-integer linear fractional programming (MILFP)

From optimization
Jump to: navigation, search

Author: Ho-Hyun Sun Steward: Dajun Yue, Fengqi You

Contents

Introduction

Mixed-integer linear fractional programming (MILFP) is a category of mixed-integer linear programming (MILP). It is similar to MILP in that it uses the branch and bound approach. It is widely used in process engineering for optimizing a wide variety of production processes ranging from petroleum refinery to polymerization processses and may even be applied to evaluation of life-cycle assessment (LCA). The unique characteristic about MILFP is that it is a non-convex MILP where the objective function to be optimized is a ratio of two linear functions and the constraints are linear </ref>. It can contain both continuous and discrete varaibles. Despite its categorization as a mixed-integer linear programming, it has characteristics of pseudoconvex/pseudoconcave objective functions, which makes optimizing to global optimal a difficult task. However, this can be solved by using largely two methods as outlined below.

Notations and Properties

A general MILFP is formulated as:


max \dfrac{A0 + \sum_{i=1}^N A1ixi + \sum_{j=1}^N A2jyj}{B0 + \sum_{i=1}^N B1ixi + \sum_{j=1}^N B2jyj}


s.t. C0k + \sum_{i=1} C1ikxi + \sum_{j=1} C2jkyj = 0, \forall k \in K


xi\ge0, \forall i \in I ,  yj\in {0,1}, \forall j \in J


with xi being continuous variables and yi being discrete variables.


The MILFP's three major properties are:

1. The objective function of the MILFP is both pseudoconvex and pseudoconcave.

2. The objective function of the MILFP is both strictly quasiconvex and quasiconcave.

3. Every local optimal solution of the MILFP is also its global optimal solution.

One thing to note about MILFPs are that their objective function contains non-convexities and non-linearities. Combined with combinatorial nature of thousands of binary variables, it makes optimizing a global solution an arduous task. It can normally be solved by mixed-integer nonlinear programming (MINLP) solvers such as SSB, DICOPT, and BARON but for cases involving large-scale MILFP such as industrial applications, such solvers are not well suited for the task. As such, MILFPs are usually transformed into one of the two methods below to solve MILFPs.

Parametric Algorithm for MILFP

One way to solve MILFP problems is using a series of parametric algorithm successively and transforming into MILPs. This method takes advantage of the MILP method to find the global optimum of the nonconvex MILFP problem and that the size of each subproblem does not change. It is similar to approaching the parametric programming as below:


 F(q) = max{N(x,y)-q, D(x,y)|(x,y)\in S}


 N(x,y) = A0 + \sum_{i=I} A1ixi + \sum_{j=J} A2jyj


 D(x,y) = B0 + \sum_{i=I} B1ixi + \sum_{j=J} B2jyj


 S:{D(x,y)>0, C0k + \sum_{i=I} C1ikxi + \sum_{j=J} C2jkyj = 0, \forall k, xi \ge 0, \forall i \in I, yj = {0,1}}


where q is a parameter, S is the feasible region of the problem.

Solving a MILFP is similar to the parametric program F(q) in that


 F(q*) = max{N(x,y) - q*, D(x,y)|(x,y) \in S} = 0


which holds only when q* = N(x*,y*)/D(x*,y*) = max {N(x,y)/D(x,y)|(x,y) \in S}

As such, the MILFP problem can be formulated through a generalized Newton's method to solve F(q) = 0.


qm+1 = qm - \dfrac{F(qm)}{F'(qm)}= qm


qm, which is the subgradient of the parametric program equation F(q) = 0, can be said to be -D(xm,ym). This is also the negative value of the denominator evaluated at the optimal solution of (xm,ym). Newton's method can be utilized to produce the following algorithm from the above eqaution:


qm+1 = qm - \dfrac{F(qm)}{-D(xm,ym)} = qm + \dfrac{N(xm,ym) - qm \cdot D(xm,ym)}{D(xm,ym)} = \dfrac{N(xm,ym)}{D(xm,ym)}


and using an iteration as described below, parametric algorithm can be used for solving MILFP problems:

STEP 1. Set q1 = 0 and initialize m by setting m as 1.

STEP 2. Solve MILP problem  F(q) = max{N(x,y)-q, D(x,y)|(x,y)\in S} and set the optimal solution as (xm,ym).

STEP 3. If 0\le F(qm) < D, create output (xm,ym) as the optimal solution. If not, continue with \dfrac{N(xm,ym)}{D(xm,ym)}e and return to step 2 to replace m with m+1 and qm with qm+1.


Note that each MILP subproblem has the same size as MILFP problem and includes |I| continuous variables, |j| binary variables, and |K| constraints and that the difference between the two is that the objective function is in a linear, parametric form.

Reformulation-Linearization Method

The reformulation is a combination of the Charnes-Cooper transformation method and Glover's linearization scheme. Charnes-Cooper transformation method cannot be applied directly to MILFP due to the fact that it can only be applied to cases where all variables are continuous which is inapplicable to MILFPs containting noncontinuous variables.However, the Charnes-Cooper method allows the MILFP to be transformed into MINLP and Glover's linearization scheme converts the MINLP into an equivalent MILP. As such, the reformulation-linearization method embraces the advantages of the two methods; the equivalent MILP from the solution need to be solved only once to obtain the optimal solution for the MILFP problem and the gap information is available during solution. The disadvantage is that the introduction of new variables and constraints increases the problem size.

MILFP to equivalent MINLP transformation

Starting with the original MILFP problem and transforming into an equivalent MINLP problem,


max \dfrac{A0 + \sum_{i=1}^N A1ixi + \sum_{j=1}^N A2jyj}{B0 + \sum_{i=1}^N B1ixi + \sum_{j=1}^N B2jyj}


s.t. C0k + \sum_{i=I} C1ikxi + \sum_{j=J} C2jkyj = 0, \forall k \in K


xi\ge0, \forall i \in I , yj\in {0,1}, \forall j \in J


B0 + \sum_{i=1}^N B1ixi + \sum_{j=1}^N B2jyj >0


New variables u = \dfrac{1}{B0 + \sum_{i=1}^N B1ixi + \sum_{j=1}^N B2jyj} and zi = \dfrac{xi}{B0 + \sum_{i=1}^N B1ixi + \sum_{j=1}^N B2jyj} = u \cdot xi is introduced.


where u>0 and zi \ge 0. The objective function can then be transformed, similar to Charnes-Cooper, into except binary variables, yj:


\dfrac{A0 + \sum_{i=I}^N A1ixi + \sum_{j=J}^N A2jyj}{B0 + \sum_{i=I}^N B1ixi + \sum_{j=J}^N B2jyj} = A0 \cdot u + \sum_{i=I}^N A1ixi + \sum_{j=J}^N A2jyj \cdot (yj \cdot u)


In addition, one of the constraints is converted into:


C0k + \sum_{i=1} C1ikxi + \sum_{j=1} C2jkyj = 0, \forall k \in K = C0k \cdot u + \sum_{i=I} C1iky \cdot xi \cdot u +  \sum_{j=J} C2jk \cdot (yj \cdot u) = C0k \cdot u +  \sum_{i=I} C1iky \cdot zi + \sum_{j=J} C2jk \cdot (yj \cdot u) = 0, \forall k \in K


1 = u \cdot (B0 + \sum_{i=I}^N B1ixi + \sum_{j=J}^N B2jy) = B0 \cdot + \sum_{i=I}^N B1i \cdot xi \cdot u + \sum_{j=J}^N B2j \cdot (yj \cdot u) = B0 \cdot u + \sum_{i=I}^N B1i \cdot zi + \sum_{j=1J}^N B2j \cdot (yj \cdot u)


As such, the original MILFP can be transformed into an equivalent MINLP problem:


max  A0 \cdot u + \sum_{i=I}^N A1ixi + \sum_{j=J}^N A2jyj \cdot (yj \cdot u)


s.t. C0k \cdot u +  \sum_{i=I} C1iky \cdot zi + \sum_{j=J} C2jk \cdot (yj \cdot u) = 0, \forall k \in K


B0 \cdot u + \sum_{i=I}^N B1i \cdot zi + \sum_{j=1J}^N B2j \cdot (yj \cdot u)


u \ge 0, zi \ge 0, \forall I \in I, yj \in {0,1}, \forall j \in J


MINLP to equivalent MILP transformation

A new variables wj = yj \cdot u is introduced again and using this, an equivalent MILP is given:


max A0 \cdot u + \sum_{i=I}^N A1izi + \sum_{i=I}^N A2j \cdot wj


s.t. C0k \cdot u + \sum_{i=I}^N C1ik \cdot zi + \sum_{i=I}^N C2jk \cdot wj = 0, \forall k \in K


B0 \cdot u + \sum_{i=I}^N B1i \cdot zi + \sum_{j=1J}^N B2j \cdot wj = 1


wj \le u, \forall j \in J


wj \le M \cdot yj, \forall j \in J


wj \ge u - M \cdot (1 - yj), \forall j \in J


u \ge 0, zi \ge 0, \forall i \in I, wj \ge 0, yj \in {0,1}, \forall j \in J


Compared to the original MILFP which has I continuous variables, J binary variables, and K constraints, the reformulation has J + 1 additional continuous variables and 3J + 1 constraints.


Applications - Cyclic Scheduling in Batch Process

MILFP can be used to for solving real life problems such as scheduling problems of multipurpose batch plants to maximize productivity. The state-task network (RTN) is shown in the figure on the right side and can be formulated as an MILFP problem. The process has four raw materials as input, six intermediates, and four products as the output. It contains five process equipment units and need eight tasks assigned to these units. Then, using the reformulation-linearization method as described above, the original MILFP problem, containing objective function of maximizing productivity, can be transformed into an equivalent MILP as formulated by Yue et al. The numerator of the objective function represents total profit and the denominator denotes the makespan. Combined with constraints for assignment, timing, capacity, demand, and material, it fully comprises a MILFP problem. The reformulation-linearization method converts this, with the addition of a new variable, into a MILP formulation.


Numerical Example

Original MILFP Problem:


Max Z = \dfrac{2x + 4u1*3u2}{x + U1 + 1}


s.t. 4x - u1 - 4u2 \le 1


5x + 4u1 + 2u2 \le 3


u = (u1,u2) \in (0,1)


x \le 0


This is transformed into:


Max Z = \dfrac{2x +4u1*3u2 - Mv1 - Mv2}{x + u1 + 1}


s.t. 4x - u1 - 4u2 \le 1


5x + 4u1 + 2u2 \le 3


u1 \le 1


u2 \le 1


x, u1, u2, v1, v2 are all bigger than or equal to 0 and u1 and u2 are integers.

where v = (v1, v2) solves

Max v1 + v2

s.t. v1 \le u1


v2 \le u2


v1 \le 1 - u1


v2 \le 1- u2


v1, v2 \ge 0


The optimal solution then becomes (x*,u*,v*) = (x*,u1*,u2*,v1*,v2*) = (0, 0.25, 1, 0, 0). Using this, this gives:


max v1 + v2


s.t. v1 \le 0.25


v2 \le 1


v1 \le 1 - 0.25 = 0.75


v2 le 1-1 = 0


v1, v2 \ge 0


Hence, the optimal solution is (x*,u*,v*) = (0,0,1).

References

1. Yue D., Guillen-Gosalbez G., You F., "Global Optimization of Large-Scale Mixed-Integer Linear Fractional Programming Problems: A Reformulation-Linearization Method and Process Scheduling Applications," AICHE, vol. 59, No. 11, July 2013, pp. 4255 - 4272.

2. Gao J., You F., "Tailored Global Optimization Algorithms for Mixed-Integer Linear Fractional Programming Problems," Retrieved from https://aiche.confex.com/aiche/2014/webprogram/Paper390654.html

3. Zsigmond I., "Mixed Integer Linear Fractional Programming by a Branch and Bound Technique," Retrieved from http://ac.inf.elte.hu/Vol_007_1987/117.pdf

4. Alemayehu G., "A Short Note on the Mixed (0,1) Linear Fractional Programming,"