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: [mg108838] Re: 0/1 knapsack-like minimalization problem and file
  • From: Daniel Lichtblau <danl at wolfram.com>
  • Date: Sat, 3 Apr 2010 06:07:42 -0500 (EST)

Peter Sisak wrote:
> 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

The variant belo will give a very good value in a couple of hours or so. 
(Caveat: might not work in version 7, though a somewhat more elaborate 
encoding does work that. Appears to be due to a bug fixed in development 
version.) It is a very simple branch-and-bound code.

closestSum4[inlist_, target_] :=
  Catch[Module[{n = Length[inlist], x, vars, obj, constraints, val,
     stack, program, counter = 0, vals, objval, soln, badvar, varvals,
     best = Infinity, bval = Infinity, bestsoln},
    vars = Array[x, n];
    obj = vars.inlist;
    constraints =
     Append[Map[0 <= # <= 1 &, vars], 0 <= obj <= target];
    stack = {{best, constraints}, {}};
    While[stack =!= {}, counter++;
     {bval, constraints} = stack[[1]];
     If[bval =!= Infinity && bval >= best, Continue[]];
     program = {target - obj, constraints};
     stack = stack[[2]];
     Quiet[vals = Minimize[program, vars]];
     If[Head[vals] == Minimize, Continue[]];
     objval = Ceiling[First[vals]];
     If[objval >= best, Continue[]];
     soln = vals[[2]];
     If[! FreeQ[soln, Indeterminate], Continue[]];
     varvals = vars /. soln;
     badvar = Position[varvals, a_Rational, {1}, 1, Heads -> False];
     If[badvar == {}, Print[{counter, target - objval, varvals}];
      bestsoln = varvals;
      best = objval;
      If[best == 0, Throw[{counter, target - best, bestsoln}]];
      Continue[]];
     badvar = vars[[badvar[[1, 1]]]];
     val = badvar /. soln;
     stack = {{objval, Join[constraints, {badvar <= Floor[val]}]},
       stack};
     stack = {{objval, Join[constraints, {badvar >= Ceiling[val]}]},
       stack};];
    {counter, best, bestsoln}]]

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;

Timing[closestSum4[bigvals, targ]]

Intermediate printout is shown below.

{116,{8148339128,0,1,1,1,1,1,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}}

{218,{8482139590,0,1,1,1,1,1,1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}}

{638,{8533400116,0,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,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,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}}

{1646,{8545165136,0,0,1,1,1,1,1,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}}

{11697,{8547289585,0,0,1,1,1,1,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,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,0,0,0,0,0,0,0,0,1,0,0}}

{11759,{8547490236,0,0,1,1,1,1,1,0,0,0,1,0,0,0,0,0,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,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}}

{25234,{8547577815,0,0,1,1,1,1,1,0,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,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0}}

{26423,{8547900672,0,0,1,1,1,1,1,0,0,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,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0}}

{93719,{8547987034,0,0,0,1,1,1,1,0,0,0,1,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0}}

{497452,{8547992942,0,0,0,0,1,1,1,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}}

As I say, it took around 2 hours to get this far. After running another 
12 hours it had proceeded no further. That's when I aborted it.

Still investigating to see whether there are useful improvements to be 
made in the ILP code.

Daniel Lichtblau
Wolfram Research




  • Prev by Date: Re: trying to use InputField as a continually attentive string input
  • Next by Date: Re: 0/1 knapsack-like minimalization problem and file
  • Previous by thread: Re: 0/1 knapsack-like minimalization problem and file
  • Next by thread: Re: 0/1 knapsack-like minimalization problem and file