[Math] How to linearize a quadratic objective function with linear constraints

constraintslinear programmingoptimizationquadratic programming

I have an optimization problem that I'm working on. The objective is defined as follows:

$Maximize: c_i\cdot w_i \cdot x_i – d_i \cdot y_i \cdot \delta_i $

subject to some linear constraints where $c_i, w_i$ and $d_i$ are scalars and

$x_i, \delta_i \in \{0,1\}$ and $y_i \in Z^+$

I wish to linearize this objective function so that I can solve it with an existing ILP solver. I found this link that suggests the following in case of a quadratic variable like $y_i\cdot\delta_i$ above:

Introduce a variable $z_i = y_i \cdot \delta_i$ w.r.t. to the following constraints:

$ L\cdot\delta_i \leq z_i \leq U \cdot \delta_i $

$ z_i \leq y_i – L\cdot(1-\delta_i)$

$ z_i \geq y_i – U \cdot (1-\delta_i)$

where: $ L \leq y_i \leq U$ are the lower and upper bounds on the values of $y_i$

Questions:

  1. Is this a common trick to linearize quadratic variables where one of them is a binary variable?
  2. How to intuitively understand this transformation so as to remember why/how it works?
  3. Are there other ways to achieve the same thing?

Best Answer

Yes, this is part of a set of standard tricks that can be used to linearize polynomial terms involving integer, and especially binary variables. There are lots of such transformations, and most good integer programming (and especially mixed integer nonlinear programming) texts summarize them.

The best way to understand the transformation is to take it on a case by case basis. First consider $\delta_i = 0$. The first set of inequalities guarantees in this case that $z_i = 0$ which is what we want, and all the other constraints are redundant. If $\delta_i = 1$, then the first set of inequalities simply enforces the bounds since $z_i = y_i$ in this case. Moreover, $1 - \delta_i = 0$ means that the last 2 constraints enforce $z_i = y_i$.

There might be other ways to transform the quadratic term. For instance you could use some Big M type models, but those are usually not desirable since they yield weak relaxations if you pick your Big M parameter wrong.

You can do away with some of the constraints if your objective function "pushes" your variables in the right direction.

Related Question