Skip to main content

Mixed integer programming

Answered

Comments

4 comments

  • Riley Clement
    Gurobi Staff Gurobi Staff

    Hi Vida,

    Do the two models produce the same objective value when solved?

    I mean I prefer continuous ones to decrease the computational time.

    If you have a model whose feasible region is given by an integral polyhedron then relaxing all variables to be continuous can result in a faster solve - but this is due to the model doing a LP presolve rather than a MIP presolve (which is more computationally expensive).  It sounds like your models do not have this property - i.e. there will always be some variables which be defined as integer.  I would not expect the model to solve faster by setting these variables to continuous - if anything I'd expect the model where they are integer to be faster because you are encoding more information into the model that can be used in the presolve routine.

    Moreover, the solving process is dependent on big M as well, which is very confusing to be determined sometimes.

    I'm sorry I don't understand this sentence, could you give some more explanation?

    - Riley

    0
  • Vida Yousefinezhad
    Gurobi-versary
    Curious
    Conversationalist

    Hi Riley,

    Thank you for your comment and apologize for my late response. 

    Regarding your first question, no, they do not produce the same objective function within a predetermined time limit (e.g., 100000). 

    As for my second issue, my model contains linear Big-M constraints, and the solving time is highly dependent on the choice M value, which is tricky.

    - Vida

    0
  • Riley Clement
    Gurobi Staff Gurobi Staff

    Hi Vida,

    The smaller the M values the better.  As the M values become larger you are more likely to experience trickle flow.  For example, if you have a constraint y <= 1000000 * x, where x is binary and y >= 0. With the default value of IntFeasTol (1e-5), x = 0.0000099999, y = 9.9999 is integer feasible, implying that y can be positive even when x is zero. Such behaviour can lead to unexpected results.  Try to use the smallest possible values of Big-M. See Dealing with big-M constraints.

    Also, please be aware that to make accurate conclusions regarding the solve time and choice of M values you need to run the model across several values of Seed and compare distributions - see How can I make accurate comparisons?

    - Riley

    0
  • Vida Yousefinezhad
    Gurobi-versary
    Curious
    Conversationalist

    Hi Riley,

    Thank you for your time. I will go through them. 

    - Vida

    0

Please sign in to leave a comment.