Finding a bounded mixed-integer solution to a system of dual network inequalities

We show that using max-algebraic techniques it is possible to generate the set of all solutions to a system of inequalities xi−xj≥bij, i,j=1,…,n using n generators. This efficient description enables us to develop a pseudopolynomial algorithm which either finds a bounded mixed-integer solution, or decides that no such solution exists.