Skip to main content

Node exploration takes too long when constraints increase




  • Riley Clement
    Gurobi Staff Gurobi Staff

    Hi Ashwin,

    The moment you introduce SOS constraints your model is no longer a LP, you have a discrete optimization problem.

    SOS Constraints are either handled by reformulation into Big-M constraints (requiring the introduction of binary variables) or via branching.  Either way the solution process will require a B&B tree.  You can control how SOS constraints are handled with the PreSOS2BigM and PreSOS2BigM parameters.

    On the screenshot on the left, presolve has reformulated all SOS constraints as Big-M constraints and introduced the required binary variables to do so.  You can infer this because there is no mention of SOS constraints in the presolved model.

    On the screenshot on the right, presolve has not reformulated any SOS constraints and they must be handled via branching.  You can infer this because there is the same number of SOS constraints in the presolved model, and no binary variables have been introduced.

    It is not surprising to me that a model with such a large number of SOS constraints may take a long time to find a feasible solution.  Perhaps you could play around with the parameters above to see if it aids the solve.

    It may also be worthwhile getting familiar with our documentation on Most important parameters including the information on our NoRel heuristic, which may prove useful here.

    - Riley


  • Ashwin Sandeep
    First Comment
    First Question

    Hi Riley


    Thank you for your explanation and suggestions. I did play around with PreSOS2BigM, MIPFocus and Threads. While changing these did help a smaller problem, even with the "optimized" parameters, the original big problem is taking too long. I realise the issue I am having is pretty much exactly the same as this post.

    Since they were unable to find a solution, I guess I woiuld also need to scale down my problem.


    Thank you again.

  • Riley Clement
    Gurobi Staff Gurobi Staff

    No problem Ashwin, I'd also recommend the recording of our webinar:

    Faster MIPs Using Custom Heuristics

    You may find some inspiration in there on creating heuristics to construct a feasible solution or using our solver as the basis for a heuristic.

    - Riley


Please sign in to leave a comment.