[Scip] Using knapsack constraint in standalone solver

[Stefan Heinz]

Hi Daniel,

Thorsten just send me the LP file.

In SCIP a knapsack constraint has to have integer weights and an integer 
capacity (internally these are "long long"). In your case that could be 
achieved by multiplying all coefficients with
10^34 if I counted right. That, however, is way larger than 
9223372036854775807 which is the maximum long long SCIP is using. 
Therefore, your constraint cannot be represented as a SCIP knapsack 
constraint. Hence, it is not upgraded and stays as a linear constraint.

Regarding the sub optimal solutions SCIP reports. That problem comes 
also form these coefficients.

I just run your file an my laptop and got the following "optimal" 
solution after 2 seconds

  objective value:                     83.7360499696736
x11                                                 1     
(obj:3.43398720448515)
x12                                                 1     
(obj:3.61091791264422)
x13                                                 1     
(obj:3.71357206670431)
x14                                                 1     
(obj:3.76120011569356)
x15                                                 1     
(obj:3.85014760171006)
x16                                                 1     
(obj:3.97029191355212)
x17                                                 1     
(obj:4.07753744390572)
x20                                                 1     
(obj:4.26267987704132)
x22                                                 1     
(obj:4.36944785246702)
x23                                                 1     
(obj:4.4188406077966)
x24                                                 1     
(obj:4.48863636973214)
x26                                                 1     
(obj:4.61512051684126)
x28                                                 1     
(obj:4.67282883446191)
x34                                                 1     
(obj:4.93447393313069)
x35                                                 1     
(obj:5.00394630594546)
x38                                                 1     
(obj:5.09375020080676)
x39                                                 1     
(obj:5.11799381241676)
x40                                                 1     
(obj:5.15329159449778)
x41                                                 1     
(obj:5.18738580584075)

Best Stefan

PS: The default infinity value for SCIP is 10^20.

On 09/02/2011 10:06 AM, Stefan Heinz wrote:
> Hi Danial,
>
>
> On 09/02/2011 04:55 AM, Daniel Jensen wrote:
>> Well, in answer to "why don't you," I'd never heard of CIP before, and I
>> can't find any documentation about it anywhere. I'm not all that great
>> with C, but as far as I can tell the search for the proper way to
>> specify a knapsack constraint in CIP ends with cons_knapsack.c line 8206:
>>
>> #define consParseKnapsack NULL
> Sorry for that. The CIP format is still a beta version.
>
> As I said in the previous mail, SCIP should detect that your linear
> constraint is a knapsack constraint during presolving. If this is not
> the case there might be a bug in SCIP. Therefore, it would be great to
> get the LP file which makes these problems.
>
> Best Stefan
>> :(
>>
>> As one might therefore expect, replacing "linear" with "knapsack" in a
>> CIP file which SCIP has written results in a crash when you try to read
>> the file.
>> _______________________________________________
>> Scip mailing list
>> Scip at zib.de
>> http://listserv.zib.de/mailman/listinfo/scip
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> http://listserv.zib.de/mailman/listinfo/scip