Sensitivity analysis for MIP

[Claas Hemig]

Hi,

I am trying to retrieve sensitivity analysis information on MIP by using GRBModel.FixedModel, but I constantly fail.

In detail:
- Create the MIP model
- Solve it (StatusCode=2)
- Create fixed model by using FixedModel
- Solve the fixed model (StatusCode=2)
- Accessing variables' values via Get(GRB.DoubleAttr.X): no error, all fine
- Accessing variables' reduced cost via Get(GRB.DoubleAttr.RC): GRBException with ErrorCode 10005

It seems that the solution of the fixed model is not a basic one, because also Get(GRB.DoubleAttr.VBasis) results in a GRBException with code 10005.

I have searched Gurobi docs, FAQ, this group, but I don't find any hint on what I am doing wrong.

Please help!

Thanks in advance

Claas

[Onur Uzunlar]

Sensitivity analysis is only applicable for LPs. There is no sensitivity analysis for IPs.

Sent from my iPhone

--
 
---
You received this message because you are subscribed to the Google Groups "Gurobi Optimization" group.
To unsubscribe from this group and stop receiving emails from it, send an email to gurobi+un...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

[Greg Glockner]

> Sensitivity analysis is only applicable for LPs. There is no sensitivity analysis for IPs.

Correct, but the original poster (OP) said he created the fixed model.

Can the OP post the log from solving the fixed model, as well as the parameters you are using?

[Claas Hemig]

On Thursday, January 9, 2014 12:54:43 PM UTC+1, RyanParker wrote:

Sensitivity analysis is only applicable for LPs. There is no sensitivity analysis for IPs.

And that's why I want to use Gurobi's FixedModel method...

originalModel.FixedModel().Get(GRB.IntAttr.IsMIP) results in 0, not 1, therefore the fixed model must be an LP (there aren't any non-linearities in the model) and therefore SA must be applicable.

[Claas Hemig]

Hi Greg,

The fixed model log:

Optimize a model with 13033 rows, 16566 columns and 85513 nonzeros

Concurrent LP optimizer: dual simplex and barrier
Showing barrier log only...

Presolve removed 11420 rows and 13111 columns
Presolve time: 0.21s
Presolved: 1613 rows, 3455 columns, 21504 nonzeros

Ordering time: 0.00s

Barrier statistics:
 AA' NZ     : 1.938e+04
 Factor NZ  : 3.680e+04 (roughly 2 MBytes of memory)
 Factor Ops : 9.905e+05 (less than 1 second per iteration)
 Threads    : 1

                  Objective                Residual
Iter       Primal          Dual         Primal    Dual     Compl     Time
   0   3.01690303e+08 -1.40290629e+05  7.04e+05 6.19e+02  2.21e+06     0s
   1   1.00929907e+08 -6.49044758e+05  2.42e+05 2.25e+02  7.13e+05     0s
   2   4.67689012e+07 -8.14262578e+05  1.16e+05 7.01e+01  3.11e+05     0s
   3   1.98042013e+07 -1.22504940e+06  4.60e+04 6.37e-12  1.33e+05     0s
   4   2.74209446e+06 -1.21046717e+06  5.72e+03 9.09e-12  1.68e+04     0s
   5   7.07026549e+05 -1.00939684e+06  1.10e+03 3.64e-12  3.37e+03     0s
   6   2.98016690e+05 -7.19936818e+05  4.18e+02 3.64e-12  1.29e+03     0s
   7   2.38564905e+05 -4.26282899e+05  2.47e+02 3.64e-12  7.41e+02     0s
   8   2.14697616e+05 -1.39865252e+05  1.28e+02 2.73e-12  3.77e+02     0s
   9   2.12508583e+05 -5.29511268e+04  5.71e+01 1.82e-12  1.91e+02     0s
  10   2.13225281e+05 -3.67290072e+02  4.81e+01 2.73e-12  1.56e+02     0s
  11   2.20815933e+05  8.99303443e+04  3.38e+01 4.55e-12  1.03e+02     0s
  12   2.26953278e+05  1.26428350e+05  2.55e+01 6.37e-12  7.63e+01     0s
  13   2.26986180e+05  1.42484474e+05  2.45e+01 6.37e-12  7.06e+01     0s
  14   2.29204257e+05  1.78687202e+05  2.02e+01 4.55e-12  5.40e+01     0s

Barrier performed 14 iterations in 0.43 seconds
Optimization interrupted


Solved with dual simplex
Solved in 1830 iterations and 0.46 seconds
Optimal objective  3.242846150e+05

The original MIP model log:

Optimize a model with 13033 rows, 16566 columns and 85513 nonzeros
Sparsify removed 3035 nonzeros (12%)
Presolve removed 10643 rows and 12279 columns
Presolve time: 0.74s
Presolved: 2390 rows, 4807 columns, 21354 nonzeros
Variable types: 4641 continuous, 166 integer (166 binary)
Optimize a model with 2390 rows, 4807 columns and 21354 nonzeros

Concurrent LP optimizer: dual simplex and barrier
Showing barrier log only...

Presolve removed 208 rows and 294 columns
Presolved: 2182 rows, 4513 columns, 20656 nonzeros

Root barrier log...

Ordering time: 0.01s

Barrier statistics:
 AA' NZ     : 1.936e+04
 Factor NZ  : 5.171e+04 (roughly 3 MBytes of memory)
 Factor Ops : 1.396e+06 (less than 1 second per iteration)
 Threads    : 2

                  Objective                Residual
Iter       Primal          Dual         Primal    Dual     Compl     Time
   0  -1.83955775e+08 -6.13956314e+08  5.05e+05 3.22e+03  9.66e+06     0s
   1  -7.10790892e+07 -6.36729836e+08  1.72e+05 7.28e-12  3.45e+06     0s
   2  -1.73395820e+07 -5.05529837e+08  4.24e+04 2.91e-11  9.08e+05     0s
   3  -3.91987363e+06 -2.66079204e+08  1.15e+04 2.91e-11  2.59e+05     0s
   4  -1.50659400e+06 -1.25521314e+08  6.09e+03 6.55e-11  1.36e+05     0s
   5  -5.50139682e+05 -7.88923912e+07  3.42e+03 2.91e-11  7.72e+04     0s
   6  -1.01447674e+05 -5.81410462e+07  1.89e+03 3.68e-11  4.35e+04     0s
   7   1.79870731e+05 -3.74966639e+07  8.19e+02 5.82e-11  1.95e+04     0s
   8   3.45659303e+05 -2.16274967e+07  2.10e+02 4.37e-11  5.89e+03     0s
   9   3.69875581e+05 -1.09842482e+07  1.06e+02 5.09e-11  2.76e+03     0s
  10   3.70531506e+05 -5.98951060e+06  5.41e+01 5.82e-11  1.36e+03     0s
  11   3.67357101e+05 -3.23458177e+06  2.96e+01 3.64e-11  7.12e+02     0s
  12   3.62687393e+05 -1.28165035e+06  1.59e+01 2.18e-11  3.30e+02     0s
  13   3.38383658e+05 -6.66763256e+05  5.07e+00 1.46e-11  1.51e+02     0s
  14   3.14639513e+05 -3.81938284e+05  2.28e+00 2.91e-11  9.18e+01     0s
  15   3.05260415e+05 -2.21432207e+05  1.65e+00 3.64e-11  6.96e+01     0s
  16   3.11584788e+05 -1.32523910e+05  1.06e+00 3.64e-11  5.55e+01     0s

Barrier performed 16 iterations in 0.38 seconds
Optimization interrupted


Solved with dual simplex
Solved in 2427 iterations and 0.39 seconds
Optimal objective  3.202846150e+05

Root relaxation: objective 3.202846e+05, 2427 iterations, 0.40 seconds

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

     0     0 320284.615    0    9          - 320284.615     -      -    1s
H    0     0                    324284.61499 320284.615  1.23%     -    1s
     0     2 320284.615    0    9 324284.615 320284.615  1.23%     -    1s

Explored 31 nodes (2826 simplex iterations) in 1.74 seconds
Thread count was 3 (of 4 available processors)

Optimal solution found (tolerance 1.00e-04)
Best objective 3.242846149878e+05, best bound 3.242846149878e+05, gap 0.0%

The non-default settings (copied from C# code):

            _env.Set(GRB.IntParam.Method, 3);
            _env.Set(GRB.IntParam.PreSparsify, 1); //reduce number of nonzeros in the matrix, only relevant for MIP
            _env.Set(GRB.IntParam.NumericFocus, 3); //handle numeric issues better (0=no focus (default) up to 3=full focus)
            _env.Set(GRB.IntParam.Threads, Environment.ProcessorCount - 1); //leave one processor untouched for other jobs running on that machine

[Ed Rothberg]

Variables are associated with models.  When you create the fixed model, you create a new set of variables.  Use model.getVars() to retrieve the variable objects for the fixed model (and query reduced costs on these).,

Ed

[Claas Hemig]

Thanks for the explanation, Ed.

One last question:
How do I make sure that I find the variable in the fixed model that corresponds to a variable in the original model? Currently I am retrieving the original variable's name by querying GRB.StringAttr.VarName and using the result as argument to fixedModel.GetVarByName(); analogously for the constraints to query on the shadow prices, for instance. (The variable and constraint names are unique.) Is this the correct/most efficient way of doing it?

Thanks

[Ed Rothberg]

 Is this the correct/most efficient way of doing it?

That's a fine way to do it.  We use hashing for GetVarByName(), so each query should have constant cost.

Ed