Дискретная оптимизация

[Paul Kellerman]

Господа математики, а также технари и экономисты! Думаю, все Вы так или иначе
сталкиваетесь с задачами дискретной оптимизации, и ломаете голову над тем, как
же получить хотя бы приближенное (субоптимальное решение). Я лично вот в свое
время сломал зубы, хвост и все остальное, подыскивая метод для решения задачи
распределения множества потребителей ресурсов по множеству поставщиков ре-
сурсов, причем сами ресурсы - многомерные. Причем понятное дело, что ни потре-
бителей, ни поставщиков нельзя было делить на какие-либо составляющие части,
например нельзя распределить 2,81 специалистов на 3,72 проектов, или же в моем
случае, нельзя распределить 5,5 виртуальных машин на 2,7 физических компьютера.
Короче, надеюсь, все поняли, о чем речь. Вопрос - как Вы решаете подобные задачи.
Особенно интересуют жадные алгоритмы, которые согласно учебникам дают гаранти-
рованно оптимальный результат, если подмножество допустимых вариантов (удовле-
творяющих системе ограничений) является специальной структурой - матроидом...
Мне не очень понятно, как именно образом можно определить (причем, чтобы это не
оказалось по сложности сопоставимо с решением самой задачи), является ли допус-
тимая область матроидом или не является. В общем буду благодарен за любые мысли.

[Carro]

в задаче обработке сигналов в распределенной системе я исходила вообще не из целей оптимизации, а из целей самого распределения. Зачем собственно делить задачи? В моем случае это было - удовлетворение требований реального времени. Если реальное время удовлетворяется, то все, больше дополнительные ресурсы не нужны и распределение сохраняется согласно некоторому найденному правилу.
Само правило строится динамически. Так как процесс жесткий по времени, то никакие сложные алгоритмы распределения не работают. нужны быстрый просто алгоритм, который обеспечит реальное время.
Правила выбора основываются на приоритетах серверов обработки. приоритеты строятся на базе взвешенной суммы характеристик - сети и серверов.