Re: 0/1 knapsack-like minimalization problem and file
- To: mathgroup at smc.vnet.net
- Subject: [mg108775] Re: 0/1 knapsack-like minimalization problem and file
- From: Daniel Lichtblau <danl at wolfram.com>
- Date: Wed, 31 Mar 2010 05:26:28 -0500 (EST)
Peter Sisak wrote:
> Hello,
>
> I tested the routine you put in, and while the speed was much more respectable than the first example, it is faulty somehow, tested on my data sets. See the following example:
>
> In[13]:= vals = {1305892864, 1385113088, 856397968, 1106152425,
> 1647145093, 1309917696, 1096825032, 1179242496, 1347631104,
> 696451130, 746787826, 1080588288, 1165223499, 1181095818, 749898444,
> 1147613713, 1280205208, 1242816512, 1189588992, 1232630196,
> 1291995024, 911702020, 1678225920, 1252273456, 934001123, 863237392,
> 1358666176, 1714134790, 1131848814, 1399329280, 1006665732,
> 1198348288, 1090000441, 716904448, 677744640, 1067359748,
> 1646347388, 1266026326, 1401106432, 1310275584, 1093615634,
> 1371899904, 736188416, 1421438976, 1385125391, 1324463502,
> 1489042122, 1178813212, 1239236096, 1258202316, 1364644352,
> 557194146, 555102962, 1383525888, 710164700, 997808128, 1447622656,
> 1202085740, 694063104, 1753882504, 1408100352}
> Out[13]= {1305892864, 1385113088, 856397968, 1106152425, 1647145093, \
> 1309917696, 1096825032, 1179242496, 1347631104, 696451130, 746787826, \
> 1080588288, 1165223499, 1181095818, 749898444, 1147613713, \
> 1280205208, 1242816512, 1189588992, 1232630196, 1291995024, \
> 911702020, 1678225920, 1252273456, 934001123, 863237392, 1358666176, \
> 1714134790, 1131848814, 1399329280, 1006665732, 1198348288, \
> 1090000441, 716904448, 677744640, 1067359748, 1646347388, 1266026326, \
> 1401106432, 1310275584, 1093615634, 1371899904, 736188416, \
> 1421438976, 1385125391, 1324463502, 1489042122, 1178813212, \
> 1239236096, 1258202316, 1364644352, 557194146, 555102962, 1383525888, \
> 710164700, 997808128, 1447622656, 1202085740, 694063104, 1753882504, \
> 1408100352}
> In[14]:= closestSum2[vals_, target_] :=
> Module[{x, vars, len = Length[vals], obj, constraints, max, best},
> vars = Array[x, len];
> obj = vars.vals;
> constraints =
> Join[Map[0 <= # <= 1 &, vars], {obj <= target,
> Element[vars, Integers]}];
> {max, best} = FindMaximum[{obj, constraints}, vars];
> {max, vars /. best}]
>
> In[23]:= Select[(vals (closestSum2[vals, 8547993600])[[2]]), #> 0 &]
> Out[23]= {1305892864, 696451130, 749898444, 1189588992, 1399329280, \
> 1178813212}
>
> The output is far from being optimal, or even close to the target value. The hand-picked list {1753882504, 1714134790, 1678225920, 1647145093, 1198348288, 555102962} for example sums to 8546839557, which is much closer to the target value than the produced output, with a sum of only 6519973922. Did a typo slip in somehow, or some artifice needs to be employed to convince Mathematica to actually do the job?
>
> Waiting for your reply
> Peter Sisak
I'm not sure what is happening with this. I did not have the patience to
let this run to completion. My guess is the underlying LP code used by
FindMinimum, interior point at machine precision, is not up to the task.
The earlier code I sent, closestSum, should give an optimal result, if
ever it finishes. It is using exact LP code, hence is slow.
You can get reasonable heuristic results using NMinimize. Here is code
for that.
closestSum3[vals_, target_, maxiters_:100,
sp_:Automatic, cp_:Automatic] := Module[
{x, vars, len=Length[vals], obj, constraints, max, best},
vars = Array[x,len];
obj = vars.vals;
constraints = Join[Map[0<=#<=1&, vars],
{obj<=target, Element[vars,Integers]}];
{max, best} = NMaximize[{obj, constraints}, vars,
Method->
{"DifferentialEvolution",
SearchPoints->sp, "CrossProbability"->cp},
MaxIterations->maxiters];
{max, vars/.best}
]
bigvals = {1305892864, 1385113088, 856397968, 1106152425,
1647145093, 1309917696, 1096825032, 1179242496, 1347631104,
696451130, 746787826, 1080588288, 1165223499, 1181095818, 749898444,
1147613713, 1280205208, 1242816512, 1189588992, 1232630196,
1291995024, 911702020, 1678225920, 1252273456, 934001123, 863237392,
1358666176, 1714134790, 1131848814, 1399329280, 1006665732,
1198348288, 1090000441, 716904448, 677744640, 1067359748,
1646347388, 1266026326, 1401106432, 1310275584, 1093615634,
1371899904, 736188416, 1421438976, 1385125391, 1324463502,
1489042122, 1178813212, 1239236096, 1258202316, 1364644352,
557194146, 555102962, 1383525888, 710164700, 997808128, 1447622656,
1202085740, 694063104, 1753882504, 1408100352};
targ = 8547993600;
In[39]:= InputForm[Timing[{sum,ones} =
closestSum3[bigvals, targ, 400, 200, 1/10]]]
NMaximize::cvmit:
Failed to converge to the requested accuracy or precision within 400
iterations.
Out[39]//InputForm=
{376.821714, {8.547888742*^9, {0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0,
1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1,
0, 0, 0, 0, 0, 0, 0, 1}}}
This gives an idea of how close we are:
In[41]:= {targ - sum, (targ-sum)/targ}
Out[41]= {104858., 0.000012267}
Percentage-wise, you cannot improve too much on this, whatever the
optimum might actually be.
One might further benefit by tweaking some other options to
NMinimize`DifferentialEvolution. I have not tried that.
One obvious practical approach you might take would be to scale down the
sizes and target, subtracting enough from the latter so that the result
will be a valid heuristic solution for the original problem. You could
then use closestSum2 with greater assurance that the result will not be
so far off the mark. Code like the following might be useful.
{smallbigvals,smalltarg} = Round[{bigvals,targ}/10^6];
smalltarg -= Length[bigvals];
InputForm[Timing[closestSum2[smallbigvals, smalltarg]]]
This variant is somewhat slower, but gives a reasonable result in a few
minutes.
{smallbigvals,smalltarg} = Round[{bigvals,targ}/10^4];
smalltarg -= Length[bigvals];
InputForm[Timing[closestSum[smallbigvals, smalltarg]]]
If I get time tomorrow I may play with alternatives to the methods I
sent earlier.
Daniel Lichtblau
Wolfram Research