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

Let \(B=(b_{ij})\) be a real \(n\times n\) matrix. The system of dual network inequalities is defined by (1) \(x_i-x_j\geq b_{ij}\) \((i,j=1,\dots,n)\). Applying max-algebra, the author shows that all its solutions can be generated using \(n\) generators. Furthermore, let \(J\) be a subset of \(\{1,\dots,n\}\), and let \((u_1,\dots,u_n)\) and \((l_1,\dots,l_n)\) be real vectors. A bounded mixed-integer solution is defined by considering~(1) subject to constraints \(u_j\geq x_j\geq l_j\) \((j=1,\dots,n)\) and requiring that \(x_j\) is an integer for all \(j\in J\). The author develops a pseudopolynomial algorithm to compute such a solution or to decide that it does not exist. If all the entries of \(B\) are integers, then a solution can be found explicitly. A note on application to scheduling completes the paper.