Linear constrained combinatorial optimization on well-described sets
Оксана Сергеевна Пичугина, Liudmyla M. Koliechkina · IOP Conference Series Materials Science and Engineering · 2021
Abstract A Horizontal method (LCCO-HM) for linear constrained combinatorial optimization (LCCO) on well-described combinatorial sets (CWDs) is offered. LCCO-HM utilizes an essential feature of the sets to solve linear unconstraint programs in polynomial time. The method belongs to the Branch and Bound group. It reduces a search domain to solutions of auxiliary unconstrained combinatorial problems and performs pruning branches based on properties of a linear function on CWDs. Applicability of LCCO-HM is justified for sets of multipermutations and partial multipermutations embedded in Euclidean space. LCCO-HM is illustrated by an example of solving a permutation-based linear optimization problem.