$2$-variable integer program with equality constraint

Question

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?

Answer 1

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:

Answer 2

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.