Modelling combinatorial optimization? problem

Question

I've been unable to match this problem into some canonical one, and I would like some guides to build/use an algorithm and solve it. Description is as follows:

---

We have some people who want breakfast. Each one may order any number of coffee, juice and toast. We accumulate the order for all the group.

InitialOrder = { C1, J1, T1 } with C1, J1, T1 being integer non-negative numbers.

Each component has a given price, so the total price of the initial order is

InitialPrice = C1 * Pc + J1 * Pj + T1 * Pt with Pc, Pj, Pt being rational positive numbers

Cafeteria has also 'breakfast menus' consisting in combinations of standard items

full breakfast = coffee + juice + toast
normal breakfast = coffee + toast
bread breakfast = 2 toast

Choosing these menus is cheaper than choosing each component separately, so we have

Pf < Pc + Pj + Pt
Pn < Pc + Pt
Pb < 2 * Pt
with Pf, Pn, Pb being rational positive numbers

People want to group the initial order into menus to minimize the total amount spent. Then

FinalOrder = { C2, J2, T2, F, N, B } with C2, J2, T2, F, N, B integer non-negative numbers

and we'll have a FinalPrice <= InitialPrice as

FinalPrice = C2 * Pc + J2 * Pj + T2 * Pt + F * Pf + N * Pn + B * Pb with Pc, Pj, Pt, Pf, Pn, Pb as rational positive numbers

All prices (Pc, Pj, Pt, Pf, Pn and Pb) are known in advance.

---

Please, do you know Which approach should I follow to build an algorithm to minimize FinalPrice for a given InitialOrder? Feel free to ask any more details you need.

Thank you in advance.

Answer 1

This looks like a Linear Integer Programming problem.

You have six variables and a linear equation (for final price) which you need to minimize, given linear constraints (must match initial order). The restriction being that the variables are non-negative and take integer values.

For instance in your example case it will be (I am presuming your actual problem is more complicated than your example :-))

Minimize

C2 * Pc + J2 * Pj + T2 * Pt + F * Pf + N * Pn + B * Pb

(Multiply Pc etc with a suitable integer to make them integers if needed)

Subject to the constraints that

   C2 + F + N = C1
   T2 + F + N + 2B = T1
   J2 + F = J1

In the general case, Integer Programming is NP-Hard, but given the small size of the problem and the constraints, standard solving techniques can probably quickly solve it for you.

Hope that helps.

Answer 2

If you don't want to go the whole hog (integer linear programming, which is a reasonably complex area), consider an exhaustive tree search using branch-and-bound. BnB is essentially depth-first search where you backtrack at any point where the cost of the current branch is greater than or equal to the best solution you have found so far.

As Moron says, though, for any large problem you're going to need ILP.

Answer 3

Since your problem is closely related to bin packing (or at least the vector version of it), some of the associated heuristics might also come in handy. Specifically, a greedy heuristic where you greedily pack full breakfasts (or 2*normal + toast depending on the relative costs) first, and then continue in this vein, might suffice.