1

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.

Martin Sleziak
  • 53,687
infiniteLoop
  • 371
  • Impossible in a pure linear form. The or operator can be translated with disjunctive constraints which cannot be done without binary variables. – Kuifje Feb 19 '16 at 14:02
  • Essentially the same question as here.. – Erwin Kalvelagen Feb 19 '16 at 18:52
  • @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 ? – infiniteLoop Feb 19 '16 at 22:13
  • @Kuifje : You think that I need a minimun of 6 binary variables in this case ? – infiniteLoop Feb 19 '16 at 22:22
  • 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. – Kuifje Feb 19 '16 at 23:26
  • In addition: a good MIP solver may even do this faster than you can do with $n$ separate LPs. A node in a B&B tree is solved typically very fast. – Erwin Kalvelagen Feb 19 '16 at 23:48
  • Thanks. I said "possibly" 64 because I know that this is a worst case scenario for branch and bound. – infiniteLoop Feb 20 '16 at 00:58
  • @ErwinKalvelagen : Do you know what technique a good MIP solver could use to be faster than solving the n separate LPs ? Maybe adding cuts using branch and cut and not only branch and bound ? – infiniteLoop Feb 20 '16 at 01:01
  • The purpose of cuts is more to keep the number of nodes down. The difference between one node and another is often just a few bounds that change. The MIP solver will exploit this as much as possible. Often a node is just few dual simplex iterations (of course not always). – Erwin Kalvelagen Feb 20 '16 at 01:12

0 Answers0