Is it possible to make a linear reformulation?

239 Views Asked by At

The question is what to do when we have a product of the three variables, quite different in their nature. One is binary, the second is real, and the third is from a discrete set of rational numbers. All variables are non-negative.

I could try to make an illustrative non-linear mix-integer program as an example

$$ \max \sum_{i\in I} (x_i y_i z_i - t_i) $$

such that

$$ \sum_{i\in I} x_i = a $$

$$ t_i \leq M x_i, \quad\forall i\in I $$

$$ t_i \geq \sum_{i\in I} y_i (x_i z_i - t_i) $$

$$ y_i, z_i, t_i \geq 0 $$

$$ x_i \in \{0, 1\} $$

$$ z_i \in P_i, \quad\forall i\in I $$

where $ P_i $ is a finite set of rational values, e.g. $ P_2 = \{1.230, 1.435, 1.577, 2.001, 2.105 \} $, and $ M $ is sufficently big real number (the big-M).

Maybe in my example there are some trivial things that I have overlooked, but which could simplify it. Nevertheless, that's not the main thing. What I'm looking for is whether we can do something with the objective function when we have a specific 3-variable product, like here. What to do with the variable $ z_i $? Can we linearize (reformulate) the program?

1

There are 1 best solutions below

5
On

One simple thing is, you formulate 2 problems, one with binary at 1, the other with binary at 0. Then the discrete one (as long as it is a finite set, say of $N$ elements) you decompose exactly the same way, getting $2N$ subproblems.

When you are done, each is a linear problem, and you have $2N$ of them, so the problem stays polynomial-time.