[Scip] scip and zimpl

[Bahador Bakhshi]

Dear Dr. Achterberg,

Before anything, thank you for your comprehensive answer.

The ''test.zpl'' is not really a simple test program. I am working on
modeling and solving a problem in computer networking (the QoS Routing
problem). My model file (cac.zpl) and all other required files are attached
to this mail.

As you can find in attached files, there are two result files.
result.txt-mps and result.txt-lp are the output of scip for the ''mps'' amd
the ''lp'' format of my problem respectively. A few lines of result.txt-mps
and result.txt-lp are as follows:

*************************************************************************************
read problem <cac.mps>
============

original problem has 5840 variables (2960 bin, 0 int, 0 impl, 2880 cont) and
3716 constraints

solve problem
=============

presolving:
....
presolved problem has 2960 variables (2960 bin, 0 int, 0 impl, 0 cont) and
801 constraints
      1 constraints of type <knapsack>
    800 constraints of type <linear>
transformed objective value is always integral (scale: 1)
Presolving Time: 0.49
****************************************************************************************

****************************************************************************************
read problem <cac.lp>
============

original problem has 5840 variables (0 bin, 2960 int, 0 impl, 2880 cont) and
3716 constraints

solve problem
=============

presolving:
...
presolved problem has 2960 variables (2960 bin, 0 int, 0 impl, 0 cont) and
801 constraints
      1 constraints of type <knapsack>
    800 constraints of type <linear>
transformed objective value is always integral (scale: 1)
Presolving Time: 3.31
****************************************************************************************

These results show that presolving in ''lp'' consumes  6.75 times more time
than ''mps''.

I would be very glad if you inform us about any issues about this problem.

Thanks in advance.


On Wed, Jun 11, 2008 at 5:38 PM, Tobias Achterberg <achterberg at zib.de>
wrote:

> 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
>
>


-- 
Best Regards.
---Bahador.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://listserv.zib.de/mailman/private/scip/attachments/20080611/f0b279a8/attachment.html
-------------- next part --------------
A non-text attachment was scrubbed...
Name: scip_test.tar.gz
Type: application/x-gzip
Size: 13609 bytes
Desc: not available
Url : http://listserv.zib.de/mailman/private/scip/attachments/20080611/f0b279a8/scip_test.tar.bin