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. 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. Then, I will recover the answer of the first $ T$ that gives 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?