I have the following function to optimize
myfunction = max(p `div` c + p `mod` c)
Here p is an array of numbers
and c is also an array of numbers
I need to find c’s which minimize the value of my function. for example if p = [1,10000]. c = 2,8 or c = 1,9 or c=5,5
number of c is length of p which is 2 (in this case). Sum of c is given as a constraint, so for example if sum is 10, then c’s can be 2,8 or 1,9 or 5,5 or 4,6 or…..etc etc. Length of c will be equal to length of p array. Hope the problem statement is clear
In haskell terms it will be,
let my_min p c = foldl1 max $ zipWith (\p c -> (p `div` c) + (p `mod` c)) p c
One way is to use various combinations of c using integer partitioning.
Now i wrote a crude parts function to do this
nparts 0 = []
nparts n = [n] : [x:xs | x <- [1..n`div`2], xs <- nparts(n - x)]
which is a bad bad example of recursion coz it’s slow!
*Main> nparts 5
[[5],[1,4],[1,1,3],[1,1,1,2],[1,1,1,1,1],[1,2,2],[1,2,1,1],[2,3],[2,1,2],[2,1,1,1]]
I can then filter this with length of p and get the required options of c
I can then call the function “ my_min” with this list (simple map application)
Problem is if i do
*Main> filter (\x->length x == 2) $ nparts 100
[[1,99]
and it hangs…for a lot of time….so time constraint?
Any other approaches to this problem to make the partitions speedier. I know it’s an optimization problem…but all non linear optizers will use floats…and fail to converge…this is an integer optimizing problem.
Any ideas??
