Minimize linear function with multiple variables

Question

So this seems like a very simple problem but I am having trouble figuring out the best approach. I may also be formulating the problem incorrectly with additional constraints I'm forgetting to explicitly state.

I need to do the following (2 variables but would like to be able to easily extend to 3 or 4 variables as well):

Minimize $$ J=T_c - N_1∗x-N_2∗y $$ with the following constraints $$ J, x,y \ge0 \\ T_c, N_1, N_2, x,y \in \mathbb{Z} $$

In other words, I'd like to minimize the function J where $T_c,N_1,N_2$ are known quantities by selecting the appropriate values for $x$ and $y$ which are non-negative integers.

I understand there can be multiple solutions. (e.g. one solution for $T_c = 60, N_1 = 6, N_2 = 12$ is $x = 10, y=0$ resulting in J = 0. Another solution is $x = 0, y=5$ resulting in J = 0 again.

After getting all the possible solutions of (x,y), I'd like to take the minimum x+y as well which is obvious after having x and y but if there is a way to integrate that into the original problem that would be convenient as well.

What's the best approach to this?

Answer 1

Firstly, $(x,y)=(0,5)$ is not an optimal solution to your initial problem as you have described it. Either the formulation is $J=T_c-N_1x\mathbf{-}N_2y$ or $N_2=-12$, since the condition on $y\geq 0$ prohibits $y=-5$.

Regardless of the above point, you could exploit the following procedure to achieve your goal.

Suppose that you have already found a solution with $J=z$ and can prove that this is the optimal $J$ value (by some method). Armed with this information, you can solve $J=z$ to find all alternate optimal solutions. This is not explicitly required though, as your goal is to then minimise $x+y$, so the condition can be included in the latter problem.

$$ \begin{aligned}\min x+y\\\mathrm{s.t.}\ T-N_1x+N_2y=z\\ X,y\geq0\\x,y\in\mathbb{Z}\end{aligned} $$

The second constraint can be included as you know that this condition must exist from your earlier observations regarding the initial problem.

In your example, since you have a solution where $J=0$ and the constraint $J\geq0$, the optimal solution must be $J=0$ ($\implies z=0$) and you can solve the new constrained problem.

Multi-objective programming, by including both minimisation conditions in the one problem maybe able to be achieved in this problem, but I believe it would overly complicate this problem.

Answer 2

You want to minimize $$ z = J = T_{\,c} - N_{\,1} x + N_{\,2} y $$ with the constraints $0 \leqslant x,y$.

The equation + constraints represent the portion of a plane, enclosed within the $z,x$ and $z,y$ planes.
So, what you have to do is geometrically clear.
Check the two lines, at the intercept of the plane with the two bounding planes $y=0$ and $x=0$
$z = T_{\,c} - N_{\,1} x$ and $z = T_{\,c} + N_{\,2} y$
then:

• if both slopes are positive, then the minimum is clearly at $x=0, y=0, z=T_{\,c} $.
• if $T_{\,c}$ is negative, and both slopes are also negative, then the minimum will be at $x,y\; \to \,\infty $
• if $T_{\,c}$ is positive, and both slopes are negative, then the minimum will be $z=0$ along the line $ - N_{\,1} x + N_{\,2} y = - T_{\,c} $.

• If ...

  (you should be able to take on and complete the cases).

Answer 3

Figured out I could formulate my problem as Mixed-Integer Linear Programming problem and using: https://www.mathworks.com/help/optim/ug/intlinprog.html

To add in the extra objective function to minimize $x+y$, I used a manual scalarization scheme.