Halloween is coming, and I am stockpiling candies. Somehow I have a crystal ball prediction that this year I will need 40 pieces of chocolate and 50 pieces of M&M. In the grocery store there are two kinds of candy bundles, one with 2 chocolate and 3 M&M each, the other one with 4 chocolate and 2 M&M each. They both cost me 3 cents each. Suppose I want to spend as much as possible, and try not to have any left-over candies, how can I figure it out systematically?
This is how we can described it in a mathematical way:
\( Min. 3x + 3y \)
\( s.t. (Subject.to) \)
\( 2x + 4y \geq 40 (chocolate) \)
\( 3x + 2y \geq 50 (M\&M)\)
Well, \(2x + 4y\) geometrically means to project a vector \((x, y)\) to a vector \((2, 4)\). The chocolate constraint basically means that the acceptable solutions must satisfy the condition: once projected to \((2, 4)\), its length needs to be greater or equal to 40. Furthermore, the solutions also need to satisfy a similar constrain for M&M, thus the region of acceptable solutions are in the grey area in the 2nd panel below.
How about the objective? Very similar: project the possible solutions to the objective axis and see which one give us the smallest value.
Well, since we can’t buy a faction of either type of candy bundle, and we have to buy integer numbers of them, the feasible solutions are actually not quite the whole grey area, but the integer grid within it. We call problems with this additional integrality constraint integer problem (IP). Note that the minimal cost we can achieve are slightly different with or without considering integrality.
In a nutshell this is what an optimization problem is all about, and the minimal objective value we can achieve is called optimal solution. In Chinese, solution is 解, which is a angle (角), a cut (刀) and a bull (牛). This is exactly the geometric intuition: rotation some angle draw some axes, make some cuts to determine the feasible region, and finally dissect the bull which is the problem.
⿰ 解
角 ⿱
刀
牛
And 解 is jiě.