I've given an optimization problem for which I want to show that it is solvable in polynomial time.
Now, I have two questions:
Can this be done by formulating a mixed-integer linear program such that the coefficient matrix A has only values of -1, 0 or +1 and show that A is total unimodular? Because solving the relaxation of this problem with appropriate LP-techniques delivers an optimal solution in polynomial time.
What alternatives do I have to show that an optimization problem is solvable in polynomial time? I'm searching for an elegant proof for writing down this result.
EDIT: I reformulated my questions and hope my request becomes clearer.