Skip to main content

When I relax a constraint, Gurobi finds a better dual bound faster. How can I use this?

Answered
Robert Hildebrand
  • Gurobi-versary
  • Conversationalist
  • First Question

I'm solving a large MILP.  I have a good solution (z = 2.05), and Gurobi is having a hard time proving a good upper bound on the problem.    The best upper bound it can find is about  z <= 3.6.   However, when I relax a set of constraints, it solves very quickly, providing an upper bound of about z <= 2.6.   

It there a way to use this upper bound that it finds in the relaxed version for the full version (aside from just enforcing z <= 2.6 manually)?

I've also tried changing the MIPFocus to 2 and 3, but this doesn't seem to change anything.

 

 

0

Comments

13 comments

Date Votes
  • Official comment
    Simranjit Kaur
    • Gurobi Staff Gurobi Staff
    This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum. Or why not try our AI Gurobot?.
  • Jaromił Najman
    • Gurobi Staff Gurobi Staff

    Hi Robert,

    You can provide the solution found in the relaxed version of your model as an initial solution, see MIP starts and Parameter Start.

    If you want Gurobi to focus on finding feasible solutions, you should set the MIPFocus parameter to 1. Setting the MIPFocus parameter to 2 or 3 makes Gurobi focus more on improving the lower bound.

    Best regards,
    Jaromił

    0
  • Robert Hildebrand
    • Gurobi-versary
    • Conversationalist
    • First Question

    The problem is phrased as a maximization.   Thus, by "dual bound", I mean an upper bound on the problem.   This is why I used MIPFocus 2 and 3.

    The solution to the relaxed version of the problem is not feasible for the original problem.   But I would like to harness the bound created from the relaxed version of the problem and apply it to the original version of the problem.

    But I do not know what GUROBI has used to determine this bound, so I cannot transfer that information to the original problem.

     

    0
  • Robert Hildebrand
    • Gurobi-versary
    • Conversationalist
    • First Question

    Here is the log data from the relaxed version of the problem.  I have the best feasible solution I have for the original problem fed into this relaxed version as a MIP start.

     

    Gurobi Optimizer version 9.0.1 build v9.0.1rc0 (mac64)
    Optimize a model with 20013 rows, 43378 columns and 76018 nonzeros
    Model fingerprint: 0xa0e339ed
    Variable types: 33456 continuous, 9922 integer (9922 binary)
    Coefficient statistics:
    Matrix range [2e-01, 2e+06]
    Objective range [1e+00, 1e+00]
    Bounds range [1e+00, 1e+00]
    RHS range [2e-02, 2e+06]

    User MIP start produced solution with objective 2.05 (0.02s)
    Loaded user MIP start with objective 2.05

    Presolve removed 19463 rows and 42902 columns
    Presolve time: 0.04s
    Presolved: 550 rows, 476 columns, 2632 nonzeros
    Variable types: 4 continuous, 472 integer (464 binary)

    Root relaxation: objective 3.883932e+00, 518 iterations, 0.01 seconds

    Nodes | Current Node | Objective Bounds | Work
    Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time

    0 0 3.88393 0 116 2.05000 3.88393 89.5% - 0s
    0 0 3.84098 0 156 2.05000 3.84098 87.4% - 0s
    0 0 3.84041 0 152 2.05000 3.84041 87.3% - 0s
    H 0 0 2.3499974 3.84041 63.4% - 0s
    0 0 3.79615 0 159 2.35000 3.79615 61.5% - 0s
    0 0 3.77506 0 163 2.35000 3.77506 60.6% - 0s
    0 0 3.71817 0 159 2.35000 3.71817 58.2% - 0s
    0 0 3.71089 0 153 2.35000 3.71089 57.9% - 0s
    0 0 3.61783 0 167 2.35000 3.61783 54.0% - 0s
    0 0 3.61783 0 163 2.35000 3.61783 54.0% - 0s
    0 0 3.61783 0 155 2.35000 3.61783 54.0% - 0s
    0 0 3.61783 0 155 2.35000 3.61783 54.0% - 0s
    H 0 0 2.3999972 3.61783 50.7% - 0s
    0 2 3.61783 0 155 2.40000 3.61783 50.7% - 0s
    H 132 149 2.4249967 3.61783 49.2% 34.1 0s
    H 1367 1015 2.4499995 3.61783 47.7% 36.5 2s
    H 1370 966 2.4749986 3.61783 46.2% 37.0 2s
    H 1372 919 2.4999991 3.61783 44.7% 37.4 2s
    H 1374 875 2.4999993 3.61783 44.7% 37.4 2s
    H 2425 1049 2.5000023 3.57305 42.9% 36.7 2s
    H 5141 1823 2.5249977 3.06327 21.3% 35.8 4s
    H 5804 2127 2.5249992 3.03926 20.4% 35.0 4s
    H 8812 2987 2.5499996 2.96386 16.2% 32.2 4s
    9134 3038 2.67474 36 20 2.55000 2.96386 16.2% 31.8 5s
    H10145 2620 2.5750000 2.96386 15.1% 32.0 6s
    H10159 2100 2.5999995 2.96386 14.0% 32.0 6s
    *14926 2113 75 2.6249997 2.77500 5.71% 33.0 7s

    Cutting planes:
    Gomory: 1
    Implied bound: 47
    MIR: 40
    Flow cover: 69
    Inf proof: 33
    RLT: 31
    Relax-and-lift: 34

    Explored 16928 nodes (565430 simplex iterations) in 8.09 seconds
    Thread count was 12 (of 12 available processors)

    Solution count 10: 2.625 2.6 2.575 ... 2.475

    Optimal solution found (tolerance 5.00e-02)
    Best objective 2.624999654307e+00, best bound 2.749726066298e+00, gap 4.7515%

    0
  • Robert Hildebrand
    • Gurobi-versary
    • Conversationalist
    • First Question

    I also just ran this with a reduced mip gap to 0.01%, which gives the tighter upper bound of about 2.65

    Optimal solution found (tolerance 1.00e-03)
    Best objective 2.649999711392e+00, best bound 2.650000642013e+00, gap 0.0000%

     

    0
  • Jaromił Najman
    • Gurobi Staff Gurobi Staff

    Hi Robert,

    It is currently not possible to pass a lower bound (or in case of maximization an upper bound) to Gurobi. Please have a look at this post and this one for a detailed explanation of why this may not be a good idea.

    What do you mean by "a relaxed version of the problem"? Did you drop some constraints or did you make some binary variables continuous?
    Could you provide the log (or parts of it) of the not relaxed problem?

    Best regards,
    Jaromił

     

    0
  • Robert Hildebrand
    • Gurobi-versary
    • Conversationalist
    • First Question

    Relaxed meaning I dropped some constraints.   I can send you the whole model and data if you want.

     

    Changed value of parameter MIPGap to 0.05
    Prev: 0.0001 Min: 0.0 Max: inf Default: 0.0001
    Changed value of parameter TimeLimit to 43200.0
    Prev: inf Min: 0.0 Max: inf Default: inf

    **Model Compiled**

    Gurobi Optimizer version 9.0.1 build v9.0.1rc0 (mac64)
    Optimize a model with 33379 rows, 43378 columns and 187878 nonzeros
    Model fingerprint: 0x3547a641
    Variable types: 33456 continuous, 9922 integer (9922 binary)
    Coefficient statistics:
    Matrix range [2e-01, 2e+06]
    Objective range [1e+00, 1e+00]
    Bounds range [1e+00, 1e+00]
    RHS range [2e-02, 2e+06]

    User MIP start produced solution with objective 2.05 (0.05s)
    Loaded user MIP start with objective 2.05

    Presolve removed 32205 rows and 41426 columns
    Presolve time: 0.09s
    Presolved: 1174 rows, 1952 columns, 7812 nonzeros
    Variable types: 1480 continuous, 472 integer (464 binary)

    Root relaxation: objective 3.883856e+00, 2262 iterations, 0.08 seconds

    Nodes | Current Node | Objective Bounds | Work
    Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time

    0 0 3.88386 0 188 2.05000 3.88386 89.5% - 0s
    0 0 3.83986 0 205 2.05000 3.83986 87.3% - 0s
    0 0 3.83986 0 209 2.05000 3.83986 87.3% - 0s
    0 0 3.79001 0 244 2.05000 3.79001 84.9% - 0s
    0 0 3.78048 0 203 2.05000 3.78048 84.4% - 0s
    0 0 3.74436 0 215 2.05000 3.74436 82.7% - 1s
    0 0 3.73654 0 241 2.05000 3.73654 82.3% - 1s
    0 0 3.71844 0 213 2.05000 3.71844 81.4% - 1s
    0 0 3.61830 0 202 2.05000 3.61830 76.5% - 1s
    0 0 3.61830 0 244 2.05000 3.61830 76.5% - 1s
    0 0 3.61830 0 221 2.05000 3.61830 76.5% - 1s
    0 0 3.61830 0 241 2.05000 3.61830 76.5% - 2s
    0 0 3.61830 0 240 2.05000 3.61830 76.5% - 2s
    0 2 3.61830 0 240 2.05000 3.61830 76.5% - 2s
    266 227 infeasible 47 2.05000 3.61830 76.5% 320 5s
    908 761 3.61830 8 215 2.05000 3.61830 76.5% 246 10s
    1416 959 3.61830 11 217 2.05000 3.61830 76.5% 229 15s
    1445 991 3.59836 18 238 2.05000 3.61830 76.5% 255 20s
    1619 1120 3.59674 24 220 2.05000 3.61830 76.5% 283 25s
    2702 1538 3.31848 41 120 2.05000 3.61830 76.5% 262 30s
    3887 1954 3.61830 28 227 2.05000 3.61830 76.5% 254 35s
    5009 2390 3.39395 31 181 2.05000 3.61830 76.5% 246 40s
    5373 2420 3.61830 35 182 2.05000 3.61830 76.5% 245 45s
    H 5376 2420 2.0500009 3.61830 76.5% 245 45s
    5987 2787 infeasible 27 2.05000 3.61830 76.5% 257 50s
    6848 3432 3.61830 31 209 2.05000 3.61830 76.5% 265 55s
    8188 4186 2.72142 48 101 2.05000 3.61830 76.5% 267 61s
    9189 4653 3.61830 32 194 2.05000 3.61830 76.5% 272 66s
    10104 4939 3.61830 35 191 2.05000 3.61830 76.5% 277 74s
    10119 5254 3.61830 36 189 2.05000 3.61830 76.5% 278 77s
    10740 5576 3.61830 26 199 2.05000 3.61830 76.5% 280 80s
    12104 6484 2.73721 39 107 2.05000 3.61830 76.5% 285 88s
    12992 6884 3.61830 29 210 2.05000 3.61830 76.5% 284 93s
    13823 7223 3.61830 33 194 2.05000 3.61830 76.5% 288 97s
    14411 7716 2.58008 49 79 2.05000 3.61830 76.5% 296 103s
    15400 7840 infeasible 31 2.05000 3.61830 76.5% 299 117s
    15637 8346 3.38753 29 224 2.05000 3.61830 76.5% 300 123s
    16531 8977 2.89225 39 114 2.05000 3.61830 76.5% 306 130s
    17711 9503 3.61830 31 232 2.05000 3.61830 76.5% 308 137s

    0
  • Robert Hildebrand
    • Gurobi-versary
    • Conversationalist
    • First Question

    (That last log is from the original model)

    I'm surprised that it gets stuck on 3.61 as the best bound that it can find.  

    0
  • Jaromił Najman
    • Gurobi Staff Gurobi Staff

    Hi Robert,

    From the logs, it seems like the BestBd can be improved only if a good enough incumbent has been found. Could you try a run with MIPFocus set to 1?

    I see you dropped ~10k constraints to obtain the relaxed problem. What kind of constraints are those? Are the constraints dense, i.e., are many variables present in these constraints? Do these ~10k constraints make all found feasible solutions of the relaxed problem infeasible? You can use the parameter SolFiles to write out all found solutions or retrieve them via solution pools in order to test their feasbility.

    Best regards,
    Jaromił

    0
  • Robert Hildebrand
    • Gurobi-versary
    • Conversationalist
    • First Question

    The complicating constraints are actually flow constraints:

    m.addConstrs(( sum(F[e[0],e[1],j] for e in H.in_edges(i)) - sum(F[a[0],a[1],j] for a in H.out_edges(i)) == X[i,j] for i in V for j in V if i != j ), name="Constraint2b")

     

     

    0
  • Jaromił Najman
    • Gurobi Staff Gurobi Staff

    Hi Robert,

    Did you try running the optimization with MIPFocus set to 1?

    You could also try treating the complicating constraints as lazy constraints. For a guide on how to implement you complicating constraints as lazy ones, please have a look here and here. For an example of how to implement lazy constraints in a user callback, please have a look at our TSP example.

    Best regards,
    Jaromił

    0
  • Robert Hildebrand
    Edited
    • Gurobi-versary
    • Conversationalist
    • First Question

     

    Yeah, MIPFocus =1 doesn't do anything.  The starting solution that I feed it is probably optimal.

    Sure, I'll try making these lazy constraints.  I'll also try a Lagrangian Relaxation to see if that recovers the bound.  Do you have a favorite GUROBI example for Lagrangian Relaxation?

     

    0
  • Jaromił Najman
    • Gurobi Staff Gurobi Staff

    Hi Robert,

    I don't have a favorite example for Lagrangian Relaxation. However, the mip1 example seems to be a good starting point for the application of such specific relaxation as it is small enough to comprehend all steps and make possible debugging easier.

    Best regards,
    Jaromił

    0

Post is closed for comments.

Didn't find what you were looking for?

New post