카디널리티 제약 선형 계획법에 대한 유한 수렴 절단 알고리즘

Abstract

The current studies finitely convergent cutting plane algorithm for a cardinality constrained linear program (CCLP), which is a linear program defined over the hypercube with an additional constraint that the number of non-zero components in the decision variable does not exceed a specified positive integer . The construction of the cutting planes is based on the fact that a solution to the linear relaxation that violates the cardinality constraint must have nonzero components. Based on this observation, the cardinality constraint can be written as a conjunctive normal form, thereby providing a facial disjunctive formulation for the feasible set of the CCLP. Leveraging this facial structure of the CCLP, we develop a specialized cutting plane algorithm that terminates within a finite number of iterations.