k-부분보형 부등식과 불확실성을 고려한 이산최적화 문제

Abstract

We define k-submodular inequalities using the definition of the k-submodular set function. These inequalities can be applied to discrete robust optimization problems with mutually exclusive constraints. We define k-submodular polyhedron associated with the k-submodular function. Also we propose a polynomial-time separation algorithm for the most violated k-submodular inequality. The computational results show the effectiveness of the proposed inequalities when solving a robust discrete optimization problem by the branch-and-cut method.