Skip to main content

Test if the start solution is feasible

Comments

13 comments

  • Silke Horn
    Gurobi Staff Gurobi Staff

    The solver cannot tell you which constraints or bounds are violated by the MIP start. You will have to test this yourself. (Iterate over the constraints/bounds and compute each violation.)

    How do you create your MIP start? Is it a complete or a partial one?

    0
  • Yauhen Yakimenka
    Gurobi-versary
    Conversationalist
    Curious

    I have a (complete) solution which (I believe) satisfies the constraints of my model - but its objective is far from optimal. After creating the variables of the model, I set the variables by calls like the following:

    v_kappa[m][q].set(GRB_DoubleAttr_Start, start.kappa[m][q])

    Here, v_kappa[m][q] is a GRBVar object created in the model (by calling v_kappa[m] = addVars(...)), and start is a structure with prepared values of my MIP start solution.

    After that, I call model.optimize().

    If Gurobi cannot tell me what constraints are violated, how can I at least make sure that I correctly understand the solver: does it think that my solution doesn't satisfy the constraints or discard the solution because of some other reasons?

    0
  • Yauhen Yakimenka
    Gurobi-versary
    Conversationalist
    Curious

    Okay, I think I found the solution here: https://www.gurobi.com/documentation/9.0/refman/start.html

    If you want to diagnose an infeasible MIP start, you can try fixing the variables in the model to their values in your MIP start (by setting their lower and upper bound attributes). If the resulting MIP model is infeasible, you can then compute an IIS on this model to get additional information that should help to identify the cause of the infeasibility.

    1
  • Brigham Frandsen
    Gurobi-versary
    First Comment

    I had the same question. I followed the guidance and set the upper and lower bounds equal to my initial solution, and the resulting model is feasible. Moreover, the objective function of the initial solution is better than Gurobi's solution, and yet I still get the message "User MIP start did not produce a new incumbent solution." How is this possible?

    2
  • Tobias Achterberg
    Gurobi Staff Gurobi Staff

    I would like to investigate. Could you please send me

    - your original model as *.mps file,

    - your MIP start as *.mst file or *.sol file, and

    - your modified model with bounds fixed to the MIP start as *.mps file?

    Please send this to achterberg (at) gurobi (dot) com.

     

    Thanks,

    Tobias

     

    0
  • Anup Agarwal
    Gurobi-versary
    Conversationalist

    I am facing the same issue,

    I provide a partial start solution (there is a unique completion to this partial solution) and Gurobi says: "User MIP start did not produce a new incumbent solution.". For this, Gurobi just keeps on running until it reaches the time limit (set to 2 mins) without even a feasible solution to the program.

    When I set the lower and upper bounds as the start solution value, Gurobi immediately terminates (as other variables are uniquely determined) and yields that the solution is feasible. The program is a mixed-integer bilinear program. Why could this be happening?

    The start solution was generated by running the same model with a subset of the original constraints (without the bilinear constraints and some other constraints) and a different objective.

    1
  • Tobias Achterberg
    Gurobi Staff Gurobi Staff

    I suspect that this is a numerical issue. When you fix the bounds of the variables to your solution values, what does Gurobi say at the end about the violations of the solution? Does it report violations that are larger than 1e-6?

    I would be interested in taking a closer look. Could you send me the *.mps and *.sol or *.mst file?

    Regards,

    Tobias

    0
  • Anup Agarwal
    Gurobi-versary
    Conversationalist

    That was the first thing I checked, the bound, constraint, and integrality violation, all are < 1e-14.

    The problem we are trying to diagnose is Gurobi taking a lot of time to find a feasible solution when the partial start solution completes to a unique feasible solution. (It was verified that the partial start was feasible by setting the variable bounds as start solution and in this scenario, the solver immediately returns). For reference for this model:

    Presolved model has 413 SOS constraint(s)
    Presolved model has 162 bilinear constraint(s)
    Variable types: 1550 continuous, 1895 integer (1742 binary)

    If I have a smaller problem then by default, the solver immediately returns (with our without partial start). I can share the model but it is fairly large for it to cause Gurobi to take time. Do I send it to: achterberg (at) gurobi (dot) com?

    There is another thing I found, if I have a much larger problem, then Gurobi has a hard time even completing the partial solution to the unique feasible solution when the variable bounds are set so that there is only one feasible solution. At this point, Gurobi just needs to solve a system of equations where each constraint has 1 unknown variable, even for this it takes >300s to find that unique feasible solution. I guess the cause of this might have something to do with either piece-wise linear constraints or quadratic equality constraints (non-convex). For reference, for this model:

    Presolved model has 2040 SOS constraint(s)
    Presolved model has 2044 bilinear constraint(s)
    Variable types: 5106 continuous, 4084 integer (2040 binary)

     

    0
  • Anup Agarwal
    Gurobi-versary
    Conversationalist

    Also, I am using version:

    Gurobi Optimizer version 9.0.0 build v9.0.0rc2 (linux64)

    I am assuming the issue referred to here: https://groups.google.com/forum/#!topic/gurobi/C1bIDPFvtKY has been fixed in that version.

    0
  • Tobias Achterberg
    Gurobi Staff Gurobi Staff

    This is really strange. Your models are not that large that they would lead to 300 seconds just for solving an equation system.

    Yes, could you please send your data to achterberg (at) gurobi (dot) com? I would like to take a closer look. Ideally, I would need the *.mps files and the corresponding *.mst or *.sol files (A *.mst file only has the integer variables, a *.sol file is the complete solution).

    Regards,

    Tobias

    0
  • Anup Agarwal
    Gurobi-versary
    Conversationalist
    import gurobipy as gp
    import random

    NUM = 10000
    UB = 8

    m = gp.Model('test')

    xs = m.addVars(range(NUM), vtype=gp.GRB.INTEGER, lb=1, ub=UB, name='x')
    ys = m.addVars(range(NUM), vtype=gp.GRB.CONTINUOUS, lb=0, name='y')
    zs = [random.random()*50 for i in range(NUM)]

    for i in range(NUM):
    m.addConstr(xs[i] * ys[i] == zs[i])

    m.setParam(gp.GRB.Param.NonConvex, 2)
    ymax = m.addVar(vtype=gp.GRB.CONTINUOUS, name='ymax')
    m.addGenConstrMax(ymax, ys)

    m.setObjective(ymax)
    m.ModelSense = gp.GRB.MINIMIZE

    # m.setParam(gp.GRB.Param.MIPFocus, 2)
    m.setParam(gp.GRB.Param.TimeLimit, 120)
    m.update()
    m.optimize()

    # """
    # Above takes around 30 to 90 seconds on
    # AMD Ryzen 5 3600 6-Core Processor (12 H/W Threads)
    # 16 GB RAM
    # """

    # Known optimal solution:
    ymax_opt = 0
    for i in range(NUM):
    xs[i].lb = UB
    this_ys = zs[i] / UB
    ys[i].start = this_ys
    ymax_opt = max(ymax_opt, this_ys)

    ymax.start = ymax_opt
    print(ymax_opt)

    m.update()
    m.optimize()

    This takes around 80ish seconds on my machine.

    This is stylistically similar to my original model, where the zs variables are set from the start solution and are not constants.
    So the above emulates the case when I set variable bounds on zs variables to fix their value.

    Surprisingly, If I change NUM to 10 times its value, the model immediately solves. So I am not sure if this would reproduce on your machine. I ran it multiple times, it does take 30 to 80s for each run for the above code.

    Here is a log for reference:

    Using license file /home/anupa/gurobi.lic
    Academic license - for non-commercial use only
    Changed value of parameter NonConvex to 2
    Prev: -1 Min: -1 Max: 2 Default: -1
    Changed value of parameter MIPFocus to 1
    Prev: 0 Min: 0 Max: 3 Default: 0
    Changed value of parameter TimeLimit to 120.0
    Prev: inf Min: 0.0 Max: inf Default: inf
    Gurobi Optimizer version 9.0.0 build v9.0.0rc2 (linux64)
    Optimize a model with 0 rows, 20001 columns and 0 nonzeros
    Model fingerprint: 0xf3277a38
    Model has 10000 quadratic constraints
    Model has 1 general constraint
    Variable types: 10001 continuous, 10000 integer (0 binary)
    Coefficient statistics:
    Matrix range [0e+00, 0e+00]
    QMatrix range [1e+00, 1e+00]
    Objective range [1e+00, 1e+00]
    Bounds range [1e+00, 8e+00]
    RHS range [0e+00, 0e+00]
    QRHS range [3e-03, 5e+01]
    Presolve added 8757 rows and 0 columns
    Presolve removed 0 rows and 2486 columns
    Presolve time: 0.13s
    Presolved: 43785 rows, 17515 columns, 87570 nonzeros
    Presolved model has 8757 bilinear constraint(s)
    Variable types: 8758 continuous, 8757 integer (0 binary)

    Root relaxation: objective 6.249121e+00, 21668 iterations, 0.12 seconds

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

    0 0 6.24912 0 14408 - 6.24912 - - 0s
    0 0 6.24912 0 14408 - 6.24912 - - 0s
    0 0 6.24912 0 14027 - 6.24912 - - 0s
    0 0 6.24912 0 13837 - 6.24912 - - 0s
    0 0 6.24912 0 13970 - 6.24912 - - 1s
    0 0 6.24912 0 12102 - 6.24912 - - 1s
    0 0 6.24912 0 12260 - 6.24912 - - 1s
    0 0 6.24912 0 9678 - 6.24912 - - 1s
    0 0 6.24912 0 9591 - 6.24912 - - 1s
    0 0 6.24912 0 8734 - 6.24912 - - 2s
    H 0 0 39.8783374 6.24912 84.3% - 2s
    H 0 0 11.5481040 6.24912 45.9% - 3s
    H 0 2 8.3300642 6.24912 25.0% - 3s
    0 2 6.24912 0 9019 8.33006 6.24912 25.0% - 3s
    197 303 6.24912 35 9562 8.33006 6.24912 25.0% 20.2 5s
    831 1252 6.24912 140 9506 8.33006 6.24912 25.0% 5.4 10s
    2109 2462 6.24912 353 9440 8.33006 6.24912 25.0% 2.8 15s
    3066 3385 6.24912 502 9306 8.33006 6.24912 25.0% 2.0 21s
    3720 4086 6.24912 611 9198 8.33006 6.24912 25.0% 1.6 25s
    4490 4902 6.24912 739 9076 8.33006 6.24912 25.0% 1.4 30s
    5303 5756 6.24912 874 8946 8.33006 6.24912 25.0% 1.2 35s
    H 6272 5959 8.3259060 6.24912 24.9% 1.0 38s
    H 6273 5661 8.3233186 6.24912 24.9% 1.0 39s
    H 6275 5380 6.9373923 6.24912 9.92% 1.0 39s
    H 6277 5111 6.9035873 6.24912 9.48% 1.0 39s
    6279 5112 6.24912 202 3081 6.90359 6.24912 9.48% 1.0 40s
    H 6279 4857 6.8974937 6.24912 9.40% 1.0 40s
    H 6282 4616 6.8931683 6.24912 9.34% 1.0 40s
    H 6314 4413 6.8916486 6.24912 9.32% 7.7 41s
    7069 5189 6.24912 77 5165 6.89165 6.24912 9.32% 7.0 45s
    8600 6001 6.34246 200 4656 6.89165 6.24912 9.32% 22.9 50s
    9953 7076 6.24912 297 4716 6.89165 6.24912 9.32% 57.0 56s
    10658 7828 6.60963 345 3878 6.89165 6.24912 9.32% 71.6 60s
    12320 8984 6.24912 469 4372 6.89165 6.24912 9.32% 95.4 66s
    H13103 8579 6.8728021 6.24912 9.07% 113 68s
    H13174 7128 6.6524118 6.24912 6.06% 113 68s
    13319 7469 cutoff 543 6.65241 6.24912 6.06% 111 70s
    14642 8235 6.24912 656 3535 6.65241 6.24912 6.06% 102 75s
    15969 9182 6.24912 751 3469 6.65241 6.24912 6.06% 100 81s
    H17207 1329 6.2491208 6.24912 0.00% 101 84s

    Cutting planes:
    MIR: 5278
    RLT: 3966

    Explored 17499 nodes (1786441 simplex iterations) in 84.48 seconds
    Thread count was 12 (of 12 available processors)

    Solution count 10: 6.24912 6.65241 6.8728 ... 8.32591

    Optimal solution found (tolerance 1.00e-04)
    Best objective 6.249120786816e+00, best bound 6.249120786816e+00, gap 0.0000%
    6.249120786816276
    Gurobi Optimizer version 9.0.0 build v9.0.0rc2 (linux64)
    Optimize a model with 0 rows, 20001 columns and 0 nonzeros
    Model fingerprint: 0x1829ebe3
    Model has 10000 quadratic constraints
    Model has 1 general constraint
    Variable types: 10001 continuous, 10000 integer (0 binary)
    Coefficient statistics:
    Matrix range [0e+00, 0e+00]
    QMatrix range [1e+00, 1e+00]
    Objective range [1e+00, 1e+00]
    Bounds range [8e+00, 8e+00]
    RHS range [0e+00, 0e+00]
    QRHS range [3e-03, 5e+01]

    Loaded user MIP start with objective 6.24912
    MIP start from previous solve did not produce a new incumbent solution

    Presolve removed 0 rows and 20001 columns
    Presolve time: 0.00s
    Presolve: All rows and columns removed

    Explored 0 nodes (0 simplex iterations) in 0.01 seconds
    Thread count was 1 (of 12 available processors)

    Solution count 1: 6.24912

    Optimal solution found (tolerance 1.00e-04)
    Best objective 6.249120786816e+00, best bound 6.249120786816e+00, gap 0.0000%

    From the log, Gurobi was able to find the correct bound but not the optimal solution. So I tried MIPFocus 2, which solves immediately. For my original problem, I was using MIPFocus 1 as it was struggling to even find feasible solutions.

    I am experimenting with my original problem if MIPFocus = 2 rectifies the high solving time, I will probably share the requested files after that.

    0
  • Anup Agarwal
    Gurobi-versary
    Conversationalist

    Also, I wanted to confirm one thing. For the below code, Gurobi saying "User MIP start did not produce a new incumbent solution" just means that it already knows the start solution right? i.e. since we are feeding it the solution it produced and it already knows it. Or could it be hinting to some problem with the start solution itself?

    In other words, is the loop marked TAG below needed in the first place?

    m.optimize()

    # TAG:
    for v in m.getVars()[:COUNT]:
    v.start = v.x
    # ^ Not all variables are explicitly assigned start value

    # Add more vars and constraints
    # Change objectives

    m.update()
    m.optimize()
    0
  • Anup Agarwal
    Gurobi-versary
    Conversationalist

    Also, I wanted to clarify, I wasn't quite correct when saying there is unique completion for the partial solution. There are more feasible solutions. Like in the above example, xs can take smaller values than `UB` as well, the solver does need to decide that.

    Having said that, I still feel the solver is taking more time than it should be.

    I ran the experiments with my original model and they are taking a similar time as before even with MIPFocus 2. There is something else going on I guess. I will share the files.

    0

Please sign in to leave a comment.