[Scip] Using knapsack constraint in standalone solver

[Dan Steffy]

Hello Daniel,

I tried solving the version you sent Thorsten with an exact precision
branch-and-bound version of SCIP that is currently under development.
It performs some operations in exact precision arithmetic with the GNU
GMP library to ensure correctness of the results.  The memory filled
up before it was able to solve to optimality, but the following
*feasible* solution was found that matches the upper bound in the
first 9 decimal digits.

-Dan


objective value:
837360170337478605725195830673672123/10000000000000000000000000000000000
x#2                                                 1
x#7                                                 1
x#8                                                 1
x#10                                                1
x#11                                                1
x#12                                                1
x#13                                                1
x#14                                                1
x#15                                                1
x#16                                                1
x#17                                                1
x#18                                                1
x#22                                                1
x#23                                                1
x#24                                                1
x#29                                                1
x#30                                                1
x#35                                                1
x#36                                                1
x#38                                                1
x#40                                                1



On Fri, Sep 2, 2011 at 7:40 PM, Daniel Jensen <jensend at iname.com> wrote:
> Hallo Stefan,
>
> I really doubt the problem needs 34 digits of precision. The cost of turning
> this into a linear constraint is that I do need a good deal of precision-
> the error in the actual product given an absolute error x in the objective
> is basically (exp(x)-1)*exp(83.736). So if there were two products from the
> set, both close to the constraint, which differed by only a couple hundred
> or less, I would need the 34 digits of accuracy to tell their logs apart.
> But I doubt any two products near that size are very close.
>
> I figured it'd probably need around the 16 digits of precision provided by a
> double. Getting more digits was no more effort on my part, and so I went
> ahead and copied the extra digits in case some solver had options for
> quad/double double precision.
>
> I knew that the DP algorithms for knapsack require integral weights but
> didn't know that that's what SCIP's solver does. I probably should have
> realized anyway that doing things in fixed point makes more sense, since the
> weights are all within an order of magnitude of each other and the dominant
> operation is addition.
>
> Scaling by a reasonable power of 10 and rounding does make it so SCIP
> recognizes this as a knapsack constraint. But even when I only scale by 10^7
> I don't think it's using its exact solver- it gives infeasible solutions and
> I get different solutions as I tighten the feastol/dualfeastol. (I really do
> need more accuracy than scaling by 10^7 gives me anyhow; scaling by 10^14
> has a good chance of being accurate enough. I'm attaching both versions.)
>
> Naive implementations of the DP algorithm require O(knapsack capacity)
> space, and AFAIK any DP solver may require that in the worst case; if SCIP's
> exact solver needs that for this problem, I'll have to give up on using SCIP
> for this and just use the brute-force idea expressed in my first email.
>
> Beste Grüße,
>
> Daniel
>
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> http://listserv.zib.de/mailman/listinfo/scip
>
>