1
$\begingroup$

As a computer scientist and not a mathematician, I know not some of the formal language to describe my problem, so I'll present it in a word problem form. Maybe someone can help me hone my search and vocabulary.

Suppose we have a set of fruits, costs, and their associated provisions

  • Apples cost \$1 and provide 1HP, 3MP, 2STA
  • Oranges cost \$2 and provide 2HP, 3STA
  • Pears cost \$3 and provide 2MP, 4STA

If I require 10HP, 7MP, and 12STA, how do I optimize for the following:

  • Generate fruit combinations which go as minimally in excess of the requirements (you know, because wasting fruit is bad)
  • Consume as few fruits as possible to fully satisfy the requirements
  • Spend as little money as possible to fully satisfy the requirements

The problem illustrated is obviously trivial, but if the number of fruits can approach dozens or even hundreds, and the number of required parameters HP, MP, STA, etc. can also reach dozens, the combinatorial space becomes computationally prohibitive, so I need another approach. What are some possible alternatives that may not be perfect, but give an asymptotically increasingly accurate answer? Some approach thoughts I've had but haven't fully pursued due to intuited problems with the approach:

  • Brute force (the permutations become innumerable and the computation time even worse)
  • Multidimensional hill-climbing algorithm with a distribution of starting points (not sure what "up" means in this approach)
  • Linear Programming (The selection process doesn't appear linear? Maybe I don't understand the formal definition of linear here)
  • Network Flow (not sure how to encode edges, and it looks like edges end up being as numerous as in the brute force approach)
$\endgroup$
2
$\begingroup$

You'll want to reduce your three listed costs to a single cost function. So, for example, give a monetary value for how much it's worth to you to get a solution using 1 less piece of fruit (all other things being equal).

Then you want to find $n_A$, $n_O$, and $n_P$, the numbers of apples, oranges, and pears, minimizing $n_A + 2 n_O + 3 n_P$, the total cost. (If you'd pay a dollar for a solution with 1 less piece of fruit, then "charge" yourself an extra dollar per fruit, bringing the cost function up to $2 n_A + 3 n_O + 4 n_P$. I'll leave it at the original values.)

You also have constraints: you want $n_A + 2 n_O \geq 10$ for HP, and $3 n_A + 2 n_P \geq 7$ for MP, and $2 n_A + 3 n_O + 4 n_P \geq 12$ for STA. In addition, $n_A, n_O, n_P \geq 0$.

The cost function and the constraints are all linear, and this is why this sort of problem is called linear programming. Since you want an integer solution (unless fractional fruit is on the table), it's a more refined version called integer programming. There are good wikipedia articles on each. (If you end up with a more complicated cost function that isn't linear, there are more general optimization choices to consider as well.)


There are standard software packages for linear and integer programming. They generally want input in matrix and vector form, and the wikipedia article on integer programming lists the canonical form to put your equations in:

Maximize $c^T x$ subject to $A x \leq b$, $x \geq 0$, and $x \in \mathbb{Z}$.

Here $x = \left(\begin{array}{c} n_A \\ n_O \\ n_P \end{array}\right)$ is your vector of how many of each to use, and is what you're solving for.

The cost function is given by $c^T x$ for the vector $c$ of coefficients. But the canonical form has a maximization, so you'll want to negate this (so when it's maximized, it's minimizing your real cost function). That is, $c = \left(\begin{array}{c} -1 \\ -2 \\ -3 \end{array}\right)$ here.

Now for the constraints: $x \geq 0$ is easy, that's just the one involving each number of fruit being nonnegative. Then we have three constraints, each involving our three numbers of fruit. This is a matrix equation, putting in the coefficients for each inequality as our rows:

$$\left(\begin{array}{ccc} 1 & 2 & 0 \\ 3 & 0 & 2 \\ 2 & 3 & 4 \end{array}\right) \left(\begin{array}{c} n_A \\ n_O \\ n_P \end{array}\right) \geq \left(\begin{array}{c} 10 \\ 7 \\ 12 \end{array}\right)$$

Since the canonical form wants $A x \leq b$, we have to negate the matrix and the vector on the right hand side while flipping the inequality:

$$\left(\begin{array}{ccc} -1 & -2 & 0 \\ -3 & 0 & -2 \\ -2 & -3 & -4 \end{array}\right) \left(\begin{array}{c} n_A \\ n_O \\ n_P \end{array}\right) \leq \left(\begin{array}{c} -10 \\ -7 \\ -12 \end{array}\right)$$

The matrix there is our $A$ and the vector on the right hand side is our $b$.

Now you can simply enter this into a standard integer programming implementation.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ What a great refresher. Your answer brought back a lot of stashed knowledge. I see now why my problem is linear. Interestingly, one of my distillations visualized yielded a tilted plane in R3 with another plane intersecting it. So apparently I was on the right track, but it gets quite confusing when you have 20+ free variables! Thanks again for your immaculate answer. I'll be referring to it for a while as I continue implementing the solution to the problem. $\endgroup$ – Buddy Nov 24 '14 at 4:12
  • $\begingroup$ Glad I could help, and best of luck on your project! $\endgroup$ – aes Nov 24 '14 at 4:37
  • $\begingroup$ I realized I had the wrong direction for the inequality for the matrix constraints (you want at least 10 HP, etc). I've edited it. $\endgroup$ – aes Nov 24 '14 at 4:45
0
$\begingroup$

The standard formulation for problems of this form is linear programming. The only problem is that the solutions may not be in integers. If integer solutions are desired, it becomes "integer linear programming".

| cite | improve this answer | |
$\endgroup$

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.