Order of variables & constraints vs. performance

Answered

Comments

3 comments

  • Daniel Espinoza

    Hi Joost,

    There are several reasons why this might happen.... first, presolve, which include probing, is almost never fully performed on all variables and combinations, instead, there are several artificial limits imposed on the process to ensure that it never takes too long (you can force presolve to work harder on your model by setting the parameter presolve=2). Also, even the linear algebra (while performing simplex pivots) will depend in the order in which variables and constraints appear... and that is natural. Of course the algorithms will re-order some of this to improve performance, but the resulting set of conditions does not uniquely define the order of variables and constraints in each basis. Also, this ordering affects the choices in which the internal heuristics works.... thus, a given order might be lucky in terms of heuristics, and thus changing the overall running time quite a lot.

    Hope this helps

    Daniel

    1
    Comment actions Permalink
  • Joost Berkhout

    Dear Daniel,

    Thanks a lot for your quick, helpful answer!

    It sounds then, that there is some optimization potential in finding a beneficial ordering for a specific type of problem.

    Kind regards, Joost

    1
    Comment actions Permalink
  • Daniel Espinoza

    Hi Joost,

    IMHO, no, there is not much to be (consistently) gain by finding the 'right' order for a problem, but there is a benefit on leaving 'related constraints' and 'related variables' close together (hopefully, define them in contiguous chunks). Of course these are loose statements.

    Daniel

    1
    Comment actions Permalink

Please sign in to leave a comment.

Powered by Zendesk