How to Linearize Non‑Linear Optimization Problems: Practical Techniques

Handling Special Objective Functions

Objective containing max/min

Introduce a new variable to replace the max/min expression, converting the original problem into a standard linear programming model. The same approach applies to min‑max problems.

Objective containing absolute values

Introduce two new non‑negative vectors to represent the positive and negative parts of the absolute value, allowing the model to be rewritten as a linear program.

Fractional objective functions

For ratio objectives such as those in Data Envelopment Analysis (DEA), substitute the ratio with new variables and add appropriate constraints. After solving the linear model, recover the original decision variables using the established relationships.

Linearizing product of binary variables

For binary (0‑1) decision variables x and y, replace the product xy with a new variable and add constraints to enforce correct logical behavior. Note that this may increase the number of variables quadratically, so its use should be considered carefully.

Handling Special Constraints

At least one of two constraints holds

Linearize the disjunction by introducing a binary variable and converting the condition into linear constraints.

Exactly one of two constraints holds

Apply a similar linearization technique, adding constraints that ensure only one of the two original constraints can be satisfied.

If one constraint holds then another holds

Linearize the implication by using a binary variable and appropriate big‑M constraints.

Piecewise Linear Function Modeling

Fixed cost constraints

In production or inventory problems, a fixed cost is incurred whenever production is positive. Model this by introducing a binary variable and a sufficiently large constant M to activate the fixed cost term.

Piecewise linear continuous functions

Many practical problems involve piecewise linear functions, such as economies of scale or marginal cost changes. Represent the function by defining breakpoints, introducing binary variables for each segment, and adding constraints that select the appropriate linear piece. Modern solvers (e.g., Gurobi, CPLEX) also support SOS‑2 constraints, which can model piecewise linear functions without manual transformation.

References: [1] 张敬信, 罗志坤, 周庆欣等编著 《数学建模算法与编程实现》 [2] 日出东方, “9种常用的线性化方法（含Gurobi中的写法）” https://zhuanlan.zhihu.com/p/63204658 [3] 金牛大王, “max函数的线性化方法” https://blog.csdn.net/m0_43401436/article/details/107127246