# When do two integer linear programs yield the same solution?

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,

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