Speeding up zero-objective binary LP

Answered

Comments

3 comments

  • Tobias Achterberg

    Do you have smaller versions of the problem that you are able to solve? If so, the tuning tool applied on those smaller versions may identify parameters that are useful also for the larger problem.

    0
    Comment actions Permalink
  • Morgan Rodgers

    I have some problems that are... well, semi-related, and MUCH smaller (most solve in 2000 seconds or less, have around 350 variables and 280 constraints). They seem to have highly variable run times, so I've set the tuning to do five runs starting with mostly default settings (only setting Presolve=2, PreDepRow=PreSparsify=1).

    One of the suggested speedups came from setting NumericFocus to 2. Another came from setting Heuristics to 0, although that did not speed up every related model.

    I think that a lot of the difficulty of the model comes from the fact that I have no objective function, and all constraints are equality constraints. I'm not sure if there are some settings for Heuristics, or for the types of cuts to use, that will help with this sort of problem.

    I'm running on a machine with 24 cores and plenty of RAM, and I'm happy to let it run for months if I have some sort of idea that it will eventually finish. But I don't entirely know how to predict this.

     

    0
    Comment actions Permalink
  • Tobias Achterberg

    Sometimes it helps to use the feasRelax model, see https://www.gurobi.com/documentation/8.1/refman/py_model_feasrelaxs.html#pythonmethod:Model.feasRelaxS

    By calling

    m.feasRelaxS(0, False, False, True)

    you are turning your model 'm' into a feasRelax model for which the constraints can be violated and in which the objective is to minimize the sum of the violations. Then, it will be very easy for Gurobi to find an initial feasible solution (with lots of constraint violations, so a high objective function penalty). During the optimization process, you will now hopefully see new incumbents with smaller violation penalty. If you are lucky, this will find a solution with 0 violation penalty, which corresponds to a feasible solution of your original model. Another lucky case would be if the dual bound becomes positive, which is a proof that your original model is infeasible (no feasRelax solution with penalty 0 exists).

     

    Regards,

    Tobias

     

    0
    Comment actions Permalink

Please sign in to leave a comment.

Powered by Zendesk