MathGroup Archive 2010

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: 0/1 knapsack-like minimalization problem and file

  • To: mathgroup at smc.vnet.net
  • Subject: [mg108789] Re: 0/1 knapsack-like minimalization problem and file
  • From: Peter Sisak <p-kun80 at hotmail.com>
  • Date: Wed, 31 Mar 2010 05:29:01 -0500 (EST)

Hello,

  Yes, I think this will be it, in the end. It works very fine and usable. I used a little tweaking myself (so as to prevent having to type in lists of that length), and used a list sort as a final step so as to facilitate selection in commonly used file manager programs without having to scroll up and down too much. For educational purposes, here's the entire code:

targetdir = "A:\bbb\cc"
SetDirectory[targetdir]
vals = Map[FileByteCount, FileNames[]]
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}]
Sort[
 Select[(vals (closestSum3[vals, 8547993600, 40, 200, 1/
       10])[[2]]), #> 0 &], Greater]
Total[%]

The number of iteration steps was downed to 40, it still produced very good (not to mention fast) results even at that setting. The Total[] was added so as to permit quick modification of the target value, should the selected files in the end not fit on the desired media after all (in effect, all media "waste" space with the used file systems and due to storage block sizes.)
  I wish to express my gratitude for your help, and also wish everyone who needs the above-written code to use it for whatever he likes and have good use of it. Of course, if there be further improvements or other approaches to the code and the original problem, I'm more than ready to test those too.

Regards
Peter Sisak

----------------------------------------
> Date: Tue, 30 Mar 2010 18:45:10 -0500
> From: danl at wolfram.com
> To: p-kun80 at hotmail.com
> CC: mathgroup at smc.vnet.net
> Subject: Re: [mg108755] 0/1 knapsack-like minimalization problem and file system access
>
> 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
>
> 		 	   		 
_________________________________________________________________


  • Prev by Date: Re: 0/1 knapsack-like minimalization problem and file
  • Next by Date: Re: a little nasty problem?
  • Previous by thread: Re: 0/1 knapsack-like minimalization problem and file
  • Next by thread: Re: floating point, step forward issue, Manipulate Appearance