Basically the problem goes like this:

We want to buy exactly one product from each category. We also want to spend as much money as possible (but within a budget $B$). So let's say we have the category "Rice" with three different brands (\$$1$, \$$2$, \$$3$) and also "Jackets" with four brands (\$$4$, \$$3$, \$$2$, \$$5$) (and many more categories, each of them with several options to choose from). Output the money spent, so it's possible to spend as much as possible, within the budget, and buying exactly one from each category (one rice, one jacket, etc).

How can we do this using Linear Programming? Let's say we have only the two products named above in the statement. We could try to maximize the function $$F = 1a + 2b + 3c + 4d + 3e + 2f + 5g$$ where each variable is one single product

Subject to:

$$1a + 2b + 3c + 4d + 3e + 2f + 5g\quad\text{$\Leftarrow$ budget}$$ $$ a+ b + c = 1$$ $$d + e + f + g = 1$$

Also, the variables $(a, b, c, d, e, f, g)$ have to be integers.

My question is: is this approach correct?

  • $\begingroup$ This problem lies in the realm of integer programming, which is somewhat tougher than LP. The problem as posed requires going as close to the budget limit as possible without exceeding it. In general, this problem for $n$ products has complexity greater than $n^k$ for any finite $k$. $\endgroup$ – Mark Fischler Aug 22 '16 at 23:12

Looks fine to me. There are a bunch of things I'd do to make it look neater, like making things into vectors so that I can write it all as dot products, but the shape of the model is right. However, the problem itself is an Integer Programming (IP) one rather than an LP one, although there are methods to either find or approximate the IP solution via an LP-relaxation (i.e. change the restriction $a, \ldots, g \in \{0, 1\}$ to $a, \ldots, g \in [0, 1]$, solve the resulting LP problem, then try to find an appropriate integer solution "close" to the LP one).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.