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