1
$\begingroup$

Do you think that there is a linear way to express this, using maybe a characteristic of this system that I cannot see. This is a set of equations involving exactly all sets of $(x_i, y_j, y_k)$ or $(x_i, x_j, y_k)$ with $i,j,k=1, ..., 3, i \ne j \ne k$):

$$1x_1 + 0x_2 + 0x_3 + 0y_1 + 1y_2 + 1y_3 = 0$$ $$\lor \,0x_1 + 1x_2 + 1x_3 + 1y_1 + 0y_2 + 0y_3 = 0$$ $$\lor \,0x_1 + 1x_2 + 0x_3 + 1y_1 + 0y_2 + 1y_3 = 0$$ $$\lor \,1x_1 + 0x_2 + 1x_3 + 0y_1 + 1y_2 + 0y_3 = 0$$ $$\lor \,0x_1 + 0x_2 + 1x_3 + 1y_1 + 1y_2 + 0y_3 = 0$$ $$\lor \,1x_1 + 1x_2 + 0x_3 + 0y_1 + 0y_2 + 1y_3 = 0$$

Knowing that :

$$x_1 \geq 0, x_2 \geq 0, x_3 \geq 0, y_1 \geq 0, y_2 \geq 0, y_3 \geq 0$$

By linear way I am talking about a set of linear equations or inequations that is equivalent, and could be put in a linear program (not a mixed integer program). The logical $or$ operator being not allowed in a linear program.

$\endgroup$
  • $\begingroup$ Impossible in a pure linear form. The or operator can be translated with disjunctive constraints which cannot be done without binary variables. $\endgroup$ – Kuifje Feb 19 '16 at 14:02
  • $\begingroup$ Essentially the same question as here.. $\endgroup$ – Erwin Kalvelagen Feb 19 '16 at 18:52
  • $\begingroup$ @ErwinKalvelagen : correct, but I put the whole problem here to see if a characteristic of it could be used to avoid the binary variables. So if I use 6 binary variables I end up with possibly 2^6 = 64 branching (using branch and bound). I am better with solving the 6 smaller linear problems right ? $\endgroup$ – infiniteLoop Feb 19 '16 at 22:13
  • $\begingroup$ @Kuifje : You think that I need a minimun of 6 binary variables in this case ? $\endgroup$ – infiniteLoop Feb 19 '16 at 22:22
  • $\begingroup$ Yes indeed, at least six. It is also true that the branching tree will have $2^6$ nodes, but only in the worst case scenario. The point of branch-and-bound is precisely not to explore all the nodes, but to close some of them with bound analysis. In all cases, 64 branching nodes is not much, and last but not least, as you pointed out you can always solve your linear program 6 times, it will do the trick efficiently. $\endgroup$ – Kuifje Feb 19 '16 at 23:26

Your Answer

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

Browse other questions tagged or ask your own question.