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,

$\endgroup$
4
  • 1
    $\begingroup$ Cross-posted: math.stackexchange.com/questions/4724197/… $\endgroup$
    – RobPratt
    Jun 30, 2023 at 12:42
  • $\begingroup$ @RobPratt what are the rules surrounding cross-posting? Should I mention it in the body of my questions? $\endgroup$
    – fool
    Jun 30, 2023 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, 2023 at 16:23
  • $\begingroup$ @RobPratt thanks for pointing this out to me. I have now noted it at the top of both questions. $\endgroup$
    – fool
    Jun 30, 2023 at 18:57

0

Your Answer

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