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

From Cornell University Computational Optimization Open Textbook - Optimization Wiki
Jump to navigation Jump to search
No edit summary
No edit summary
Line 20: Line 20:
# Numbered list item <math>\Q(x,y)</math> is (strictly) pseudoconcave and pseudoconvex over its domain.  
# Numbered list item <math>\Q(x,y)</math> is (strictly) pseudoconcave and pseudoconvex over its domain.  
# Numbered list item The local optimal of <math>\Q(x,y)</math> is the same as its global optimal.
# Numbered list item The local optimal of <math>\Q(x,y)</math> 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.

Revision as of 20:16, 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:

The properties of the objective function are shown as follows:

  1. Numbered list item is (strictly) pseudoconcave and pseudoconvex over its domain.
  2. Numbered list item The local optimal of 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.