Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations
https://hochbaum.ieor.berkeley.edu/html/pub/EJOR-3var.pdf
IPの制約がMonotoneのときは、minCutに帰着して多項式時間でhalfintegral解が求まるっぽい。目的関数は非線形でもいいらしい。
あとで読む。