Solution with start values better than bound on "real" solution?

[Thomas S.]

Hallo all,

when solving a large minimization problem that got stuck at an LB of 23800 and incumbent of 24300 after about 80000 seconds, I wondered if I could speed up the solution by using Start, VarHintVal and BranchPriority on some key decision variables.

The resulting problem now already knows an incumbent of 23600 after 600 seconds. So the solution has become better than the previous LB by only specifying hints for the search, not by changing any equations.

Gurobi (version 6.5 on a Windows 64-bits system) gives me the following warning at the beginning of the optimization: "Model contains large matrix coefficient range". Therefore, I am using NumericFocus=3, but I suspect that I have to put a little more effort into this problem than just setting one solver option.
Since the problem is quite large, I do not want to go through the model creation process line by line. Is there something like the IIS for infeasibility problems for my numeric problem? Some option that lists me the constraints with the largest and smallest coefficients?

My matrix coefficients range from 3e-6 to 2e8, the RHS from 4e1 to 2e8 (according to the log in my console). I suppose since the standard tolerance is somewhere around 1e-6 that the coefficients should be in a similar range. Is this assumption correct or are there any rules or guidelines for this topic?

Thanks a lot in advance.

Best wishes,
Thomas

[Kostja Siefen]

Hi Thomas,

Finding a feasible solution with objective value 23600 seems impossible if you already know a dual bound of 23800 for your minimization problem. Can you post a log? 

A good rule of thumb is to keep your coefficients within a range of 6 orders of magnitude. The best way to archive this is usually to manually scale your model.

You can always inspect the numerical quality of your solution after an optimization run (see section "Solution quality attributes" at http://www.gurobi.com/documentation/6.5/refman/attributes.html).

Best wishes,

Kostja

[Thomas S.]

Hello Kostja,

I know. To my understanding this could not have happened, because the lower bound is a theoretical bound and the incumbent is a real solution that is supposed to be greater or equal to this bound. Therefore, I assumed that this problem might originate from numerical problems. In earlier attempts without NumericFocus=3, I even ran into problems with infeasible or unboundedness.

Attached you find the log of the now terminated run with start values, varhintval and branchpriority (start.log) as well as the one without (standard.log). The calculation with start values has - as you can see - finished now. Interestingly, the solver did not touch my start values, although (from my understanding of the problem), they cannot be optimal.

Thank you for your advice regarding the scaling and numerical quality. Since I am not an optimization expert, can you please tell me which of these attributes might be relevant to my problem or direct me to a good source to understand the meanings of scaled or unscaled violations, etc.

Best wishes,
Thomas

[Tobias Achterberg]

Hi Thomas,

it is very likely that your model features numerical issues (rather than Gurobi
having a bug that leads to a global lower bound that is larger than the
objective value of some feasible solution).

Unfortunately, Gurobi (and also no other MIP solver as far as I know) provides
features to better understand the numerical issues in a model. Something like an
IIS procedure that extracts a small sub-model with numerical issues would
certainly be very handy, but this would be pretty hard to implement.

You should be able to easily find the small and large matrix coefficients in
your model yourself. Just implement a loop that goes through all rows in the
model and check the coefficient values.

For continuous models, Gurobi automatically applies scaling. This means to
multiply the rows and the columns with some values with the goal of bringing all
matrix coefficients closer to 1 in absolute terms. Scaling a row by scaler s > 0
means to multiply all coefficients and the right hand side by s. Scaling a
column by scalar s > 0 means to multiply the matrix coefficients and the
objective coefficient of the variable by s and dividing the bounds by s.

There are different scaling options available in Gurobi, see the parameter
"ScaleFlag" parameter.

Of course, scaling the model implicitly modifies the feasibility tolerances. For
example, if a constraint is scaled by 1e-2, then the default feasibility
tolerance of 1e-6 for this row is implicitly increased to 1e-4, because a
violation of 1e-6 in the scaled model means a violation of 1e-4 in the original
model. This is the reason why solutions with "unscaled infeasibilities" may
occur. In a post-processing step we try to clean those up by doing a few simplex
pivots on the original (unscaled) model, but this may fail. Additionally,
presolving is another source for generating internal solutions that turn out to
be slightly infeasible when the internal solution is transformed back to a
solution of the original user model.

For (mixed) integer models, scaling is not applied. The reason is that scaling
integer variables is incompatible with the integrality requirement: if you scale
an integer variable by 2, then the integrality requirement turns into "the
variable must be a multiple of 0.5", which is something that our solving
algorithm does not support. For this reason, it is particularly important for
MIPs that the user tries to control the matrix coefficients himself. This can be
done by completely changing the model or just by scaling. Scaling the rows
should be trivial. Scaling the columns involves some model knowledge. For
example, it is often not necessary to specify Dollars in Cents as integer
variables if the model talks about millions or billions of Dollars. In this
case, it might be better to model this in terms of millions of Dollars, which
means that the decision variables would become continuous variables (ignoring
the fact that a solution may then not exactly correspond to a valid Dollar and
Cent amount). Going from Cents to millions of Dollars means to scale the column
by a factor of 1e+8.

For example, if you model the costs for cruise ships (just learned that the big
ones with capacity for 5000 passengers cost about 700 millions of Dollars), your
constraint with the "Cent" version would look as follows:

min y
s.t. 7e+10 x - y = 0 // cost of a ship
5000x >= 12000 // need ships for 12000 passengers
x >= 0
0 <= y <= 1e+12 // budget is 10 billion dollars

with x integer being the number of ships to buy and y integer being the Cents to
pay for the cruise ships. Now, going from Cents to millions of Dollars means to
scale y by 1e+8, which yields

min 1e+8y
s.t. 7e+10 x - 1e+8y = 0 // cost of a ship
5000x >= 12000 // need ships for 12000 passengers
x >= 0
0 <= y <= 1e+4 // budget is 10 billion dollars

Finally, you can scale the objective function and the first constraint by 1e-8
and the second constraint by 1e-3 to get

min y
s.t. 700 x - y = 0 // cost of a ship
5x >= 12 // need ships for 12000 passengers
x >= 0
0 <= y <= 1e+4 // budget is 10 billion dollars

This looks like a much more reasonable model in terms of numerics.


Regards,

Tobias

[Thomas S.]

Hello Tobias,

thank you very much for your detailed answer.

I managed to scale the coefficients and the results look much better now (the computation was also faster).
My problem's matrix range is now between 1e-4 and 1e+3.

Best wishes and thanks again,
Thomas