[Scip] Using knapsack constraint in standalone solver

Stefan Heinz heinz at zib.de
Fri Sep 2 22:41:02 MEST 2011


Hi Daniel,

I checked both version. In both case SCIP omits the DB algorithm since 
the expected required memory would be to much. If it would use the DB it 
would solve a single knapsack problem during presolving.


You can turn SCIP into an enumerator by doing:

SCIP> set lp solvefreq -1
SCIP> set numerics feastol 1e-12
SCIP> opt

This lead in case of knapsack266_e7.lp to enumeration. Doing this, 
however, requires a lot of memory using SCIP.

Let us know if your brute force method worked.

Best Stefan

On 09/02/2011 07:40 PM, Daniel Jensen 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



More information about the Scip mailing list