A heuristic solution for a knapsack problem: using Excel’s VBA to optimize a sequence of Solver problems
Suppose we have to bill our business partner in the total amount of $500 000, but it’s our policy, that one invoice contains no more than $50 000 worth of records. This could be stated to be a kind of a curious knapsack problem. At first, the model is run and an initial invoice is created – worth of up to $50 000 –, followed by the removal of those records from the dataset. Then the model is run again, the chosen records are once again removed and so on – until we have created a minimal number of invoices, all filled to the maximum possible capacity. This is, though, stated with notion, that we are actually only using a heuristic method: each time the $50 000 solution is found to the remaining problem, and this is all that is taken into account. Ideally, we should look at the entire picture at once and find the global optimum of record allocation. This model was created for my optimization modeling class.