LP modelling question... long time since school

Question

Sure, this isn't a programming question, per se... but I couldn't think of a better place to ask it all the same.

I'm writing an application that ultimately will assist a shopped to determine how to achieve the greatest savings on a specific site. The site provides two prices for just about every product - a regular price and a discounted price. The discounted price is available to anyone, but only one discounted item can be added to any given order. With just that information, the incentive is to minimize your order siz and instead place multiple orders. On the other hand, the total shipping costs are determined by the order size (by weight) and so the incentive there is to maximize the order size and place just one order.

I'm looking for a model to determine the most efficient way to balance the orders given the available discount for one item and the weight's influencing the shipping costs for the order(s).

I'm remembering back to school enough that I think this is a linear programming problem... but all I can remember about that class was how confusing it was.

Anyone have any tips on how to go about the math for this program?

Answer 1

This isn't regular linear programming, this is integer linear programming. The former is solvable in O(n²), the second is NP-hard.

Some variant of the branch-and-bound algorithm should be applicable to your program. If you don't feel like implementing it yourself, available libraries include GLPK, COIN-OR and CPLEX.

Answer 2

Expanding on my comment above, this problem depends heavily on the precise structure of the shipping costs. Suppose that the shipping costs are linear with a (potentially) non-zero constant term. Namely, shipping cost = C + Rw, where C and R are constants and w is the weight of an order. Then, it turns out that the optimal solution is simple: group every item where the discount is less than C into one order and order each item where the discount is greater than C separately (left as an exercise for the reader). In the degenerate case where C = 0, you would simply place a separate order for each item.

On the other hand, if the shipping cost has more of a threshold structure -- e.g.: if the weight of a shipment is less than B then the cost is C1 but if it's greater than B then the cost is C2 -- the situation becomes a form of the NP-complete bin-packing problem. I should note here that just because a situation is shaped like an NP-complete problem that you shouldn't immediately give up hope. For many real-world situations, good heuristics exist and it's entirely possible that the range of real-world inputs restricts the problem to manageable instances.

In real life, the odds are that the shipping costs are probably a combination of a bunch of different things (e.g.: maybe piece-wise linear with discontinuities) which makes modeling the problem that much harder. But, I hope I've demonstrated that it's crucial to have a clear idea of how these costs are structured in order to understand your problem.