[Scip] scip and zimpl

[Tobias Achterberg]

Hi Bahador,

> Q1- Why does not zimpl create binary variables when output format is the 
> lp format?
> 
> I have following variable in test.zpl file:
> 
> X [F * F] binary;
> 
> after creating the test.lp file (zimpl -O test.zpl), I tried to solve 
> the problem using scip. The output message from scip indicates that 
> there is not any binary variable. After presolving, all the variables 
> are converted to binary variables.
> 
> I tried the mps output format (zimpl -O -t mps test.zpl). In this case 
> the original problem has binary variables and presolving consumes less 
> time than previous case.

Although it is possible to add a BINARY section to .lp files, zimpl just puts all integer 
and binary variables to the GENERALS section. This is no harm, since binary variables and 
integer variables with bounds 0 <= x <= 1 are identical.

SCIP reads the GENERALS variables and assigns a type "INTEGER" to them. In presolving, it 
detects that these are integers with bounds 0 <= x <= 1 and converts them into binaries. 
It is, however, unclear to me why this consumes any noticeable time. It would be nice if 
you can send us the test.zpl file.


> Q2-  I ask this question because I am not an expert in Integer 
> programming. I saw many times in output message from scip that there are 
> non-integral values in the "dual sol" column. How is it possible to have 
> a non-integral dual ''intermediate solution'' (before finding the 
> optimal solution) for MIP problem?

The "dualbound" column of the SCIP output shows you the proven dual bound of your problem 
instance. If you have a minimization problem, the dual bound gives a lower bound on the 
optimal objective value.

The global dual bound (which is shown in the "dualbound" column) is the worst (i.e., 
smallest in case of minimization) of the dual bounds of all remaining open leaf nodes in 
the search tree. The dual bounds in the leaves are calculated by solving an LP relaxation. 
And because integrality is relaxed in the LPs, the objective value can be fractional. 
Hence, the "dualbound" can also be fractional.

If you have a pure IP (all variables integer), and if your objective coefficients are 
integral numbers, then of course every feasible solution will have an integral objective 
value. Therefore, you can always round up (in case of minimization) the "dualbound". SCIP 
does not do this in the output (and also not internally) because even the changes in the 
fractional part of the objective value provide valueable information. For example, if you 
see dual bounds that evolve like this:

13.0405
13.0891
13.1321
13.2342
13.3874
13.4923

then you can see that there is some progress. If SCIP would just print

14.0000
14.0000
14.0000
14.0000
14.0000
14.0000

you cannot see whether the optimization is stuck or whether something happens.



Best, Tobias