Avoid Symmetry
Mkc 7
- Ran into unsolveable subproblems
- The culprit: symmetry
- One knapsack, 66 identical colored items, all with similar cost/weight ratios, and almost half of the items fit into the knapsack
- Found a better IP feasible soln than previously know in less time it took just to solve the LP relaxation of the natural formulation
Try to break up the symmetry - even if arbitrarily
If two decisions, each of which can take 5 values, which would you choose?
- x e {1,2,3,4,5} y e {1,2,3,4,5}
- Z e {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25}
Binary expansion vs. linear expansion
- y = 20x0+ 21x1 + 22x2 + 23x3 + 24x4
- y = 1x1+ 2x2 + 3x3 + 4x4 + 5x5