# $2$-variable integer program with equality constraint

I have an integer program with variables $x, y \in \{0,1,\dots,m\}$. Somehow, I can prove that

1. the cost function will strictly decrease with both $x$ and $y$.

2. an optimal solution should satisfy $x+y=k$.

Do I still need to do linear search over $x \in \{0,1,\dots,k\}$? Or are there other simpler solutions?

ADD: I am wondering if I can substitute $y$ with $k-x$ so that the original problem is reduced to integer programming with just one variable $x$. Let's say the cost function becomes $f(x)$. And by computation, $f(x)$ will be minimized at $x^*$. Can I just search around $x^*$ and get the optimal solution?

• How can you search "around $x^*$" when $x^*$ is unknown and is the solution ? – Yves Daoust Jun 4 '18 at 21:39
• I am thinking the cost function is reduced to a one-dimensional function $f(x)$. So I can minimize $f(x)$ first to get $x^*$ (and $k-x^*$). Then I ASSUME that the optimal solution is around $(x^*,k-x^*)$. So I can just search around $(x^*,k-x^*)$. But I am not sure if the assumption is right or not. – Paradox Jun 5 '18 at 2:49
• Don't you realize that the optimal solution is $(x^*,k-x^*)$ ? So your proposal amounts to: 1) find the optimal solution, then 2) search in the vicinity of the optimal solution. – Yves Daoust Jun 5 '18 at 6:23
• That's exactly my question. Can we guarantee that the optimal integer solution is in the vicinity of $(x^*,k-x^*)$? – Paradox Jun 5 '18 at 19:16
• In the end I understood what you mean. In your mind, $x^*$ is not integer and you find it with an "ordinary" solver (assuming that by some magic you can solve for the continuous case). Then this is a bad idea because the integer solution may very well be far from the continuous solution. – Yves Daoust Jun 5 '18 at 19:27

It is of course better to eliminate one of the unknowns to get a one-dimensional problem.

Anyway, when doing so, $c(x, k-x)$ loses the montonicity property and it is not even sure that it is unimodal. So exhaustive search is safer.

Update:

The integer minimum might not coincide with the continuous minimum. For the sake of illustration:

• so, as described in the problem, the optimal solution is not guaranteed to be near $(x^*,k-x^*)$? – Paradox Jun 5 '18 at 2:43

Unless you have more information about the cost function such as a discrete differential equation there is no simpler way.

I am assuming $m\geq k$ and that you are looking for the optimal solution and not a pseudo-optimal solution.

• The first order discrete differential equation (regarding both $x$ and $y$) is strictly less than 0. So I am claiming that the cost function will decrease with both $x$ and $y$. – Paradox Jun 4 '18 at 21:02
• Yes, but it seems that you have no been given any information on the relation between the discrete partial derivatives of x and y. So without that I don't see any other option. – Runge Kutta Jun 4 '18 at 21:11
• Response to the edit in your question: To find $x^*$ you would have to be given $f(x)$ or $\frac{df(x)}{dx}$, making the solution trivial so I'm assuming you were not given these. – Runge Kutta Jun 4 '18 at 21:19