Open AccessLinear constrained combinatorial optimization on well-described sets
Author(s) -
Oksana Pichugina,
Liudmyla Koliechkina
Publication year - 2021
Publication title -
iop conference series. materials science and engineering
Language(s) - English
Resource type - Journals
eISSN - 1757-899X
pISSN - 1757-8981
DOI - 10.1088/1757-899x/1099/1/012064
Subject(s) - permutation (music) , mathematics , combinatorial optimization , pruning , linear programming , euclidean space , euclidean geometry , domain (mathematical analysis) , algorithm , combinatorial explosion , mathematical optimization , computer science , combinatorics , mathematical analysis , physics , geometry , acoustics , agronomy , biology
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.