My binary programming problem is:
max: (a1 * x1) + (a2 * x2) + ..... + (an * xn)
subject to:
(c1 * x1) + (c2 * x2) + ..... + (cn * xn) < C
n = 10
a1, ... an, c1, ... cn, C are known
x1, ... xn are binary
This is a process task assignment problem. In my case, the overhead of solving the binary/integer programming problem needs to be very small (< 1 millisecond). When I run this with the CBC solver / lpsolve, it reports time of 2ms - 7ms. I dont have SCIP/Gurobi. Is there any way to solve this in less than a millisecond? Does it even seem to be reasonable to expect to solve this in less than a millisec?
(I did disable the printf's in CBC. But i am not sure if there are any other system operations that it is stuck with.... any log files it is writing)
This is the standard knapsack problem which can be solved efficiently using dynamic programming. This has been discussed nicely in the knapsack wiki (and also in mutiple stack overflow posts e.g. here DP algo for knapsack and here recursive knapsack)
The c++ implementation measures ~20us on my core i7 @3Ghz