1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ How can you search "around $x^*$" when $x^*$ is unknown and is the solution ? $\endgroup$ – Yves Daoust Jun 4 '18 at 21:39
  • $\begingroup$ 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. $\endgroup$ – Paradox Jun 5 '18 at 2:49
  • $\begingroup$ 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. $\endgroup$ – Yves Daoust Jun 5 '18 at 6:23
  • $\begingroup$ That's exactly my question. Can we guarantee that the optimal integer solution is in the vicinity of $(x^*,k-x^*)$? $\endgroup$ – Paradox Jun 5 '18 at 19:16
  • $\begingroup$ 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. $\endgroup$ – Yves Daoust Jun 5 '18 at 19:27
1
$\begingroup$

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:

enter image description here

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

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.

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Paradox Jun 4 '18 at 21:02
  • $\begingroup$ 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. $\endgroup$ – Runge Kutta Jun 4 '18 at 21:11
  • $\begingroup$ 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. $\endgroup$ – Runge Kutta Jun 4 '18 at 21:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.