[Scip] Using knapsack constraint in standalone solver

[Daniel Jensen]

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
-------------- next part --------------
A non-text attachment was scrubbed...
Name: knapsack266.zip
Type: application/zip
Size: 1372 bytes
Desc: not available
Url : http://listserv.zib.de/mailman/private/scip/attachments/20110902/d4b8a3ab/knapsack266.zip