- 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
- https://stackoverflow.com/questions/56122889/how-to-control-ordering-of-matlab-optimproblem-variables
- 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
I am trying to understand point 1 and point 2 here. Do you mean to say that there is no point in adding symmetry breaking constraints?
ReplyDeleteNo I am not talking about (symmetry is an important issue). What in my opinion is not so important is to worry about the variables are ordered in memory of the solver. The model has say x[i,j], y[i,k], z. The solver has: x1,x2,x3,x4... How this is mapped is not something worry about.
Delete