Re: 0/1 knapsack-like minimalization problem and file
- To: mathgroup at smc.vnet.net
- Subject: [mg108840] Re: 0/1 knapsack-like minimalization problem and file
- From: Peter Sisak <p-kun80 at hotmail.com>
- Date: Sat, 3 Apr 2010 06:08:05 -0500 (EST)
Hello,
Thank you for your intense work so far on the subject, I am very much impressed by it. I am honestly getting the impression that going this deep, the exploration and comparison of all the strategies employed so far would already amount to a paper - since as you yourself also pointed out, it is an NP-complete problem as a form of the "subset sum" problem, and it might have a number of other uses. Furthermore, one additional thing occured to me, for this particular problem at least: since the sector size on a standard CDs and DVDs is almost exclusively 2048 byte nowadays, it would be safe to add a "divide by 2048 then round up" step, perhaps it would help with making the optimisation quicker (smaller numbers to handle, add, compare, etc.) Just an idea to test.
Best regards
Peter Sisak
----------------------------------------
> Date: Fri, 2 Apr 2010 12:01:47 -0500
> From: danl at wolfram.com
> To: p-kun80 at hotmail.com; mathgroup at smc.vnet.net
> Subject: Re: [mg108755] 0/1 knapsack-like minimalization problem and file system access
>
> 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
>
>
_________________________________________________________________