2
$\begingroup$

This question is cross-posted from math stack exchange

An illustrative example

Consider an integer linear program $\min -2x_1 + x_2$ subject to $x_1 - x_2 \leq 3$ and $x_1 + x_2 \leq 10$ and integer $x_1, x_2 \geq 0$.

The solution is $x_1=10, x_2=0$.

I can change the objective's coefficient from $-2x_1 + x_2$ to $-5x_1 +2x_2$ and the solution would be the same. The first constraint be similarly perturbed with no change in the solution.

Notation

Let an integer linear program be defined by a three-tuple $P_i = (c_i, A_i, b_i)$, i.e., $\min c'x$ subject to $Ax\leq b$. A solution of $P_i$ is denoted $S_i = \{x: x = \text{argmin } c_i'x, A_ix \leq b_i\}$.

Questions

For the following questions, assume the solutions are unknown.

  1. Generally, when and how do I determine whether two integer linear programs $P_1, P_2$ yield the same solution?

  2. How do I know what to what degree I can perturb the coefficients in $c, A, b$ without changing the solution?

In the above, by "the same solution" or "without changing the solution", I mean two scenarios: 1. the scenario where the solutions are identical, i.e., $S_1 = S_2$, and 2. the scenario where the solutions overlap $|S_1 \cap S_2| \geq 1$ but are not necessarily equal,

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Cross-posted: math.stackexchange.com/questions/4724197/… $\endgroup$
    – RobPratt
    Jun 30 at 12:42
  • $\begingroup$ @RobPratt what are the rules surrounding cross-posting? Should I mention it in the body of my questions? $\endgroup$
    – user
    Jun 30 at 16:05
  • $\begingroup$ Cross-posting is generally discouraged, but if you do so, please mention it in both questions. See the bottom of or.stackexchange.com/help/on-topic $\endgroup$
    – RobPratt
    Jun 30 at 16:23
  • $\begingroup$ @RobPratt thanks for pointing this out to me. I have now noted it at the top of both questions. $\endgroup$
    – user
    Jun 30 at 18:57

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.