Ask HN: 0/1 Decision variables vs. bounded integers for selection problem

3 points by steve_g 4 years ago | 3 comments

I'm asking here because I know there are some smart optimization experts on HN. I tried Reddit, but no joy.

In my production planning problem, I want to select around 1000 items from a set of 15000 items to process in a given day. There are multiple constraints to satisfy and new items come in every day. It’s very much like a multi-dimensional knapsack problem with some extra constraints.

Each item has its own identifier and they are truly unique items. But they can be grouped for practical purposes so that (let’s say) 10 items could be represented by a single value and set of multi-dimensional costs.

I’d like to know whether it’s generally better for a MIP solver to represent selection of items by ten 0/1 decision variables or one integer decision variable that must be < 11 for ten items in a group. I know if I use the ten variables I’d also need to do something to break symmetry of solutions – like maybe add a term to minimize items IDs in the objective function.

I’d appreciate any thoughts or pointers to good resources on this. Thanks.

elonmollusc 4 years ago |

I recall discussing this in an integer programming class many years ago, and being told that binary variables were the better option. This Stack Exchange post seems to confirm:

https://or.stackexchange.com/questions/3209/how-to-choose-be...

The answer, which sounds reasonable to me, is that branching on a binary variable fixes its value, which effectively reduces the dimensionality of the model in subsequent evaluations. Branching on an integer variable restricts its range, but keeps it in the model. It may be easier to add cuts to the binary model.

I also have a copy of Wolsey's Integer Programming that I flipped through, but couldn't find anything clearly relevant to the question.

From a modeling perspective, if you care about the selection of individual items, then individual binary variables seem to be the natural choice. Trying to "compress" ten binary selection variables into an integer from 0 to 10 will be indirect and you'll probably have to add a bunch of extra constraints to encode that a variable assignment like x_c = 2 corresponds to selecting item #2 from category c.

(I have done some OR in the past but I'm not an expert on MIPs, so I defer to anyone with better knowledge.)

nanis 4 years ago |

One thing that is missing from your problem statement is the objective function. What are you trying to maximize?

steve_g 4 years ago | |

I would be a combination of total mass of the items plus some terms that reflect inventory demand - like weight_factor* (actual_inventory - target inventory)*planned_production for an item category. If I have too much of a category, processing more of the category is rewarded.