6

Lets assume a complex production system that is fed by tasks of type $A$ (e.g. $A$ = deliver material) . Within a horizon of interest $H$, a number $N$ of tasks $A$ can be performed. The model of the problem results in a difficult MILP.

Solving the relaxed model for $N=1, N=2, N=3, ... , N=5$, I obtain the following values for the objective function (maximization). $$ \begin{align} & N=1 & 1000.0 \\ & N=2 & 1200.0 \\ & N=3 & 2100.0 \\ & N=4 & 2100.0 \\ & N=5 & 1800.0 \\ \end{align} $$ Can I assume, that setting $N=3$ will not cut off the optimal solution of the original problem?

Clement
  • 2,252
  • 7
  • 13

2 Answers2

1

In general, you cannot assume that setting N=5 will not cut off an optimal solution. Because you do not know the MIP objective value, but just that of the (LP?) relaxation. This objective value could be arbitrarily far away from the optimal objective value of the MIP.

Dan
  • 21
  • 2
0

I'm moving my last comment to an answer.

Assuming the values stated (1000 for $N=1$ etc.) are optimal values for the LP relaxations, the fact that the maximum with N=5 is less than the maximum with N=3 indicates that there are solutions to the relaxation with N=3 that are not feasible when N=5. That implies that it is possible that the solution to the integer model with N=3 might not be feasible when N=5. So no, you cannot be sure the solution with N=3 is optimal for N=5.

Edit: My original answer (below) was for the original question, which has since been clarified, and is irrelevant to the clarified version.

It's unclear what "the original problem" is. Assuming that $N$ appears only as an upper limit in the constraints (e.g., $n\le N$), you can safely say that any solution that is optimal for a given value of $N$ will remain feasible (though possibly not optimal) for any $N^{'} > N$.

prubin
  • 39,078
  • 3
  • 37
  • 104
  • "The original problem" is the formulation where N=5. The question is, given the pattern for the values of the relaxed problems for N=1, N=2, N=3, N=4, N=5 can I conclude that solving the MILP problem for N=3 leads the solution to the MILP for N=5? – Clement Feb 26 '22 at 09:35
  • Is $n$ a variable or a parameter in the model? – prubin Feb 26 '22 at 17:08
  • I see, there is a misunderstanding here. N is a parameter, n is not needed. I edited the question. – Clement Feb 26 '22 at 17:48