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 Answer 1

Reset to default
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$
1
  • $\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$ Commented Aug 12, 2014 at 22:02

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.