0

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)

ctrlAltDel
  • 1
  • 3
  • Just a comment, but the big commercial solvers (Gurobi, CPLEX, Xpress) put their R&D effort into solving larger and harder problems - they may not be much better than the open/free solvers for very small instances. If you know that you have a specific problem structure you may be able to get a simpler implementation to run faster as it does not need to provide all the possible functionality that the general solvers provide. Think about restricting pre-solve, removing most or all cuts and heuristics unless they really help your problem, disabling any callbacks etc. Sort-of a RISC MIP solver. – TimChippingtonDerrick May 01 '15 at 10:25
  • Do you mean max? The solution to the above should always be the zero vector. – Chris Hagmann May 01 '15 at 13:57
  • Thanks TimChippingtonDerrick for the response. After digging in more, i realized that this is the standard knapsack problem which can be solved efficiently using dynamic programming. The c++ implementation measures ~20us. I will post a reply with this. – ctrlAltDel May 01 '15 at 14:54
  • hi Christopher, oops, yes that was supposed to be 'max'. Editing the question now. – ctrlAltDel May 01 '15 at 14:56

1 Answers1

0

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

Community
  • 1
  • 1
ctrlAltDel
  • 1
  • 3