[Scip] scip and zimpl

Bahador Bakhshi bakhshi at gmail.com
Sat Jun 14 08:01:22 MEST 2008


 Hi Michael,

I changed the "General" section to "Binary" in the generated lp file and
test again. Now scip reports that all variables are "bin" (in the "General"
case, all variables are reported as ''int''), but it HAS NOT ANY EFFECT on
presolving time.

I think that we should wait for new release of scip.

On Fri, Jun 13, 2008 at 4:13 AM, <michael.winkler at zib.de> wrote:

> Hi Bahador,
>
> if you test your lp file after changing the generals to binaries you will
> see no effect in presolving time of the lp file.
>
> The difference between the presolving times of both file formats (lp, mps)
> results from different approaches on problem creation.
>
> Precisely, it's based on the different order of variables and constraints
> in created problem and the sorting methods used during presolving.
>
> The (old) sorting methods have been changed and in the next SCIP release
> there won't be such great presolving time differences (on your problem).
>
> Best, Michael
>
> > 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.
> > _______________________________________________
> > Scip mailing list
> > Scip at zib.de
> > http://listserv.zib.de/mailman/listinfo/scip
> >
>
>


-- 
Best Regards.
---Bahador.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://listserv.zib.de/mailman/private/scip/attachments/20080614/b677912a/attachment.html


More information about the Scip mailing list