1
$\begingroup$

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?
$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Any recommendations on texts? I'm also intrigued by the Big M. I "have" seen and worked with something with large "M"s and have been told that's a trick without really understanding why. Pointers would be much appreciated. $\endgroup$ – PhD Aug 12 '14 at 22:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.