[Scip] Using knapsack constraint in standalone solver

[Thorsten Koch]

Dear Daniel,

could you send the LP file? ((g)zipped if possible)

Best regards
Thorsten

Am 01.09.2011 21:33, schrieb Daniel Jensen:
> 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

-- 
The important thing is not to stop questioning.
Curiosity has its own reason for existing.          -- Albert Einstein
______________________________________________________________________
Dr. Thorsten Koch / Konrad-Zuse-Zentrum für Informationstechnik Berlin
www.zib.de/koch  /          Takustraße 7, 14195 Berlin-Dahlem, Germany
koch at zib.de     /                     Phone +49-30-84185-213, Fax -269
_______________/  DFG Research Center "Matheon"  http://www.matheon.de

Kooperativer Bibliotheksverbund Berlin Brandenburg  http://www.kobv.de
______________________________________________________________________