LEXICOGRAPHIC EQUIVALENCE IN MIXED COMBINATORIAL OPTIMIZATION OF LINEAR-FRACTIONAL FUNCTIONS ON ARRANGEMENTS

摘要

The paper substantiates the method of constructing the lexicographic equivalence to solve mixed combinatorial optimization problems on arrangements with linear-fractional objective function and linear additional constraints. The method involves directed search of equivalence classes obtained by splitting polyhedral set using equivalence relation. The authors propose exact methods as well as an approximate one. The approximate method allows getting the objective function value that differs from the optimum by no more than a predetermined value.