I am a beginner in Integer Linear Programs and I have a question about a problem that I am dealing. This problem tracks a configuration of a graph by unitary transformations on the graph and I want to minimize these number of transformations to achieve another configuration of the graph. As I only allow exactly one transformation per step, minimizing the number of transformations is the same as minimizing the number of steps.
But, I enter in the following problem: There is no internal property that can be tracked so that I can check if one or other state is closer or farther from the wanted configuration. That means that I can only check if a specific sequence of transformation is correct in a prior-of-execution defined step, for example, $T$. Then, what I am thinking in doing is testing a range of values for $T$, as there is a polynomial upper-bound for this value, in increasing order (bound in the number of steps). Then I recover the answer of the first $T$ that gives me any answer, as I know it will be a optimal answer.
My questions are:
- This sort of is a feasibility test for a fixed $T$, as if the polytope exists, any answer will be a optimal answer, as they all have the same number of steps $T$. This approach is possible? In the sense that it can be calculated given a infinite amount of time? Because I am not sure what is the behavior of a IL program when there is no possible answer (ie. no polytope).
- If yes, there is some existing technique to deal/optimize this type of situations without finding a specific property?