Confusion regarding model.optimize() and model.feasRelaxS(1, True, False, True) output

PraveenRB Source

I have modeled the MILP problem.

When executed the code

m.Optimize()

Output looks like this:

Optimize a model with 798001 rows, 312006 columns and 2117780 nonzeros
Variable types: 1920 continuous, 310086 integer (310080 binary)
Coefficient statistics:
 Matrix range [3e-01, 2e+04]
 Objective range [1e-01, 9e+02]
 Bounds range [1e+00, 3e+04]
 RHS range [3e-01, 3e+04]
Presolve removed 725090 rows and 191031 columns
Presolve time: 3.22s

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

Solution count 0

Model is infeasible
Best objective -, best bound -, gap -

But when executed below code:

copy1 = m.copy()

if m.status == GRB.INFEASIBLE:
 copy1.feasRelaxS(1, True, False, True)
 copy1.optimize()

Output looks like this:

Solve phase I feasrelax model to determine minimal relaxation

Optimize a model with 798001 rows, 1114022 columns and 2919796 nonzeros
Model has 802016 quadratic objective terms
Variable types: 803936 continuous, 310086 integer (310080 binary)
Coefficient statistics:
  Matrix range     [3e-01, 2e+04]
  Objective range  [0e+00, 0e+00]
  QObjective range [2e+00, 2e+00]
  Bounds range     [1e+00, 3e+04]
  RHS range        [3e-01, 3e+04]
Found heuristic solution: objective 3.175944e+24
Presolve removed 1620 rows and 64056 columns (presolve time = 6s) ...
Presolve removed 1620 rows and 64056 columns
Presolve time: 5.59s
Presolved: 796381 rows, 1049966 columns, 2909656 nonzeros
Presolved model has 800396 quadratic objective terms
Found heuristic solution: objective 3.169464e+24
Variable types: 802316 continuous, 247650 integer (247650 binary)

Here it specifies model has Quadratic Objective terms.

Can somebody guide me what exactly difference between these two? and why it is giving model has Quadratic terms?.

pythongurobimixed-integer-programming

Answers

answered 4 days ago sascha #1

You call feasRelaxS with arguments (1, True, False, True). The docs say:

feasRelaxS ( relaxobjtype, minrelax, vrelax, crelax )

If you specify relaxobjtype=1, the objective of the feasibility relaxation is to minimize the sum of the squares of the bound and constraint violations.

So the sum of squares is not linear and Gurobi needs to use some non-linear solving-approach. If QP or SOCP or whatever, that's Gurobi's decision.

This is where those quadratic terms are introduced: sum of the squares of the bound and constraint violations.

The output:

Found heuristic solution: objective 3.169464e+24

also looks like your model is quite far away from being feasible i would say.

Edit: Or maybe not. As non-Gurobi user i was under the impression, that's the final result. But you trimmed your output and this is just an early heuristic result and we can't say much about the unknown final result at this point!

The general question about what is it doing is answered by the doc-sentence:

The feasibility relaxation is a model that, when solved, minimizes the amount by which the solution violates the bounds and linear constraints of the original model

Meaning: you don't care anymore about your original objective, but about a new one, which expresses how bad some solution is in terms of violating constraint- and variable-bounds.

(Side-note: all this is explained in the docs and to be honest: Gurobi has very good documentation compared to some competitors in my opinion! So use it and don't call functions without knowing what they are doing)

comments powered by Disqus