[Scip] Using knapsack constraint in standalone solver

[Stefan Heinz]

Hi Daniel,

First, SCIP has a method which is capable to solve a knapsack problems 
using dynamic programming. It can be even called via the callable 
library (SCIPsolveKnapsackExactly())
http://scip.zib.de/doc/html/cons__knapsack_8c.html#a8f16a4931b2d53b5ad471c7ec62f8a0e

Second, all constraints which are parsed form an LP or MPS file are 
first created as linear constraints. In the first rounds of presolving, 
SCIP detects different special linear constraints. One of them are  
knapsack constraints. That means in presolving your linear constraint 
should be replaced by a knapsack constraint.

Third, in case only one knapsack constraint is present in the whole 
problem, SCIP tries to us the dynamic programming approach to solve it 
(SCIPsolveKnapsackExactly()). There are cases, however, were this is 
omitted.

To check what the problem is in your case, it would be nice if you send 
use the LP file (it should not be to big I guess) and the output of 
SCIP. That would help us to get more insides.

Regarding the documentation for using SCIP as a standalone solver, there 
will be a tutorial with the next release. Thanks for pointing that out.

Best Stefan



On 09/01/2011 09:33 PM, Daniel Jensen wrote:
> I'm having a hard time finding much documentation for using SCIP as a
> standalone solver. I have a problem where I want to find the maximal
> product from a set of 42 integers which does not exceed a given number;
> the obvious thing to try was to take logarithms and turn it into a
> subset sum/0-1 knapsack type problem, and I put together simplistic
> versions of this in AMPL and LP formats and tried using SCIP to solve.
>
> Apparently ("display constraint") SCIP is using its linear constraint-
> it doesn't recognize that the inequality in my file is a knapsack
> constraint. I imagine that if I could tell it this was a knapsack
> constraint and use the exact knapsack solver I'd be in a much better
> position. How can I use the knapsack solver without writing my own C
> program?
>
> (long-winded detail below)
>
> If I simply run SCIP on my LP file, it spends only 13 seconds arriving
> at a solution which is rather suboptimal. Displaying the solution shows
> that though all variables were specified to be binary it's assigning one
> of the variables a value of 1.00000099175524, bringing the objective
> value exactly up to the bound. So I need to decrease the tolerances esp.
> for integrality. But after I reduce tolerances, it chews through all my
> memory in ten minutes and starts swapping. (After about half an hour I
> interrupted it and found that though it had found a better solution it's
> still suboptimal.) Well, this is a large problem and my machine only has
> a couple GB of memory, but I can't help wondering whether there's a
> better way to do this with SCIP. (The naive brute-force approach of
> splitting the collection in two, finding the sums for all 2*2^21 subsets
> of each, and matching each in one group with the largest member of the
> other group to which it can be added without going over the limit should
> be much faster than that and take much less memory.)
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> http://listserv.zib.de/mailman/listinfo/scip