On a quasistability radius for multicriteria integer linear programming problem of finding extremum solutions

Abstract

We consider a multicriteria integer linear programming problem with a targeting set of optimal solutions given by the set of all individual criterion minimizers (extrema). In this study, the lower and upper attainable bounds on the quasistability radius of the set of extremum solutions are obtained when solution and criterion spaces are endowed with different Hlder’s norms. As a corollary, an analytical formula for the quasistability radius is obtained for the case where criterion space is endowed with Chebyshev’s norm. Some computational challenges are also discussed.

Рассматривается многокритериальная задача целочисленного линейного программирования с целевым набором оптимальных решений, каждое из которых минимизирует хотя бы один из критериев, т.е. является экстремумом. В данной работе нижние и верхние достижимые оценки радиуса квазиустойчивости множества экстремальных решений доказаны в ситуации, когда в пространствах решений и критериев заданы различные нормы Гёльдера. В качестве следствия получена аналитическая формула радиуса квазиустойчивости для случая, когда в пространстве критериев задана норма Чебышёва. В работе также кратко обсуждены некоторые вопросы, связанные с вычислимостью.

Розглянуто багатокритерійну задачу цілочисельного лінійного програмування з цільовим набором оптимальних розв’язків, кожен з яких мінімізує хоча б один з критеріїв, тобто є екстремумом. Нижні та верхні досяжні оцінки радіуса квазістійкості множини екстремальних розв’язків доведено у ситуації, коли у просторах розв’язків та критеріїв задані різні норми Гeльдера. Як наслідок отримано аналітичну формулу для радіусу квазістійкості у випадку, коли у просторі критеріїв задана норма Чебишова. У роботі також коротко обговорюються деякі питання пов’язані з обчислюванністю.