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$
7
  • $\begingroup$ How can you search "around $x^*$" when $x^*$ is unknown and is the solution ? $\endgroup$
    – user65203
    Jun 4, 2018 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, 2018 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$
    – user65203
    Jun 5, 2018 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, 2018 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$
    – user65203
    Jun 5, 2018 at 19:27

2 Answers 2

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$
1
  • $\begingroup$ so, as described in the problem, the optimal solution is not guaranteed to be near $(x^*,k-x^*)$? $\endgroup$
    – Paradox
    Jun 5, 2018 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$
3
  • $\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, 2018 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$ Jun 4, 2018 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$ Jun 4, 2018 at 21:19

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .