Tuesday, May 14, 2019

Ordering of variables / constraints in an LP/MIP

In [1] a user asks about how to force a certain ordering of variables for an LP/MIP model. This is an intriguing question for me because I really never worry about this.

  • The user asks only about variable ordering. Of course there is a symmetry here: the same question can be asked for equations. Well, equations correspond to slack variables, so this is essentially the same.
  • A different ordering may (will?) cause a different solution path, so you can expect different solution times and iteration counts. Of course, this is in a very unpredictable way, so not something we can exploit easily. Especially in MIPs we have this concept of performance variability [2]: minor changes in the model can cause significant different solution times.
  • Why would you really worry about the ordering? There are three cases I can think of: (1) access variables by index number [I tend to use higher-level tools where this is not needed], (2) when implementing some decomposition scheme [same: in higher-level tools we can index by names], or (3) when plotting the non-zero elements in the A matrix [I never do this; I find this is not adding much insight into the model].  In practice, I never worry about the ordering. We have already many things to worry about when building LP/MIP models; this should not be one of them. 

I don't understand why one would want to spend time on this.

References

  1. https://stackoverflow.com/questions/56122889/how-to-control-ordering-of-matlab-optimproblem-variables
  2. Andrea Lodi, Andrea Tramontani. Performance Variability in Mixed-Integer Programming. In INFORMS TutORials in Operations Research. Published online: 14 Oct 2014; 1-12, https://pubsonline.informs.org/doi/abs/10.1287/educ.2013.0112

No comments:

Post a Comment