How to efficiently solve the following optimization problem?
Find $a$ and $b$ which minimize $ c = a * b $ under the constraints $ c \geq C $, $ a \leq A $, $ b \leq B $, where $a, b, A, B, C$ are positive integers.
Obviously the problem is challenging only if $ A < C $ and $ B < C $.
I cannot think of a solution which does not involve going through many $a$ and finding the best $b$ for each $a$. But the problem does sound very simple (it's just product!) so I'm wondering if there is a faster way.
I have drawn a graph showing the feasible region (the points marked on the graph) for a particular example:
The curve is $y=\frac Cx$. It crosses the line $y=B$ at $(\frac CB, B)$ and it crosses the line $x=A$ at $(A, \frac CA)$
I would suggest the following algorithm to suggest which of the red points minimises $xy$. It should be obvious that we do not need to consider any of the blue points above a red point.
Leftmost red point is found by calculating $x_0=\left \lfloor \frac CB \right \rfloor$ and $y_0=B$. Gives us our best (so far!) value of $C_{min}=x_0y_0$. Let $x_{best}=x_0$ and let $y_{best}=y_0$
Let $x_1=x_0+1$. Calculate $y_1=\left \lfloor \frac C{x_1} \right \rfloor$. Compare $C_1=x_1y_1$ with $C_{min}$. If $C_1<C_{min}$ then let $x_{best}=x_1$ and let $y_{best}=y_1$.
Continue like this with $x_{n}=x_{n-1}+1$ until $x_n=A$.
To make this more efficient you should set $A<B$ - that way you will have fewer values to test.