# Integer Linear Program as a feasability test 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? Posted on Categories proxies