2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Решение системы линейных однородных неравенств особого вида
Сообщение14.04.2010, 19:48 


14/04/10
2
Мне необходимо практически тоже самое что и человеку
http://dxdy.ru/post207253.html#p207253
С той только разницей, что количество неизвестных у меня порядка 10-20, количество неравенств -- десятки тысяч, возможно сотни тысяч или больше (фактически это обучающее множество, для которого мне хочется иметь максимальную долю выполненных неравенств).
Особенность задачи в том, что коэффициенты всех неравенств небольшие целые числа близкие к 0 - фактически это столбцы состовленные как разности двух других столбцов с небольшими неотрицательным целыми числами. При том сумма этих чисел в изначальных столбцах почти всегда меньше размерности системы.
Может кто знает какие эвристики тут могут подойти, где стоит об этом почитать. Я пока не нашел ничего полезного. Пытаюсь делать лучевой поиск добавляя по одному неравенства и строя системы фундаментальных решений неравенств и запоминая сколько неравенств на каждой из этих систем нарушено (на каждом шаге выбирая только k областей в которых меньше всего нарушений неравенств). Но такой подход кажется не очень хорош -- размер систем фундаментальных решений растут в худшем случае экспоненциально, а на деле это оказывается вычислительно слишком сложно. А лучше пока придумать ничего не удается.
Хочется идей или классических статей по этому поводу.

 Профиль  
                  
 
 Re: Решение системы линейных однородных неравенств особого вида
Сообщение19.04.2010, 14:58 


17/10/08

1313
Данную задачу можно свести к частично-целочисленной задаче линейного программирования. Для каждого уравнения будет добавлена одна псевдобулева переменная, принимающая значение ноль, если ограничение «удовлетворено»; и единицу – если «не удовлетворено». Критерий – минимизация суммы псевдобулевых переменных.

После этого можно воспользоваться хорошим пакетом линейного программирования (например, бесплатным пакетом CBC или платным CPLEX) – система сама найдет оптимальное решение. Насколько мне известно, коммерческие системы позволяют решать задачи с миллионами переменных и ограничений. Маловероятно, что для этой задачи вручную написанная программа даст сколь-нибудь сравнимый результат в сравнении с пакетами линейного программирования.

 Профиль  
                  
 
 Re: Решение системы линейных однородных неравенств особого вида
Сообщение20.04.2010, 21:38 


14/04/10
2
Большое спасибо за ответ, я как раз некоторе время назад пришел к подобному выводу: полезно использовать готовые пакеты решающие задачу линейного программирования. То есть сводить эту задачу к задаче линейного программирования добавляя переменные связанные с нарушением неравенств (оказывается, полезно их делать даже не булевыми, а просто с физическим смыслом "мера нарушения неравенства"). В частности я нашел несколько эвристик в статьях Chinneck'а подходящих к задаче MaxFS (maximum feasible subsystem) которую я оказывается решаю :)
А подумав и еще чуть-чуть (ну и почитав), начал осознавать что вроде можно это свести и к задаче решаемой при помощи SVM и прочих классических методов машинного обучения. Что очень даже разумно, учитывая откуда появилась задача и сильную мусорность данных.
Суть - как только я осознал что эта задача называется именно так, я без труда начал находить то, что мне нужно - статьи, эвристики и прочее. Конечно писать все с нуля в данном случае не только долго, но и вредно, так как пишу управляющий код я на питоне, и лучше использовать готовые стандартные пакеты решения стандартных задач написанные на си и вызывать их из питона. Чем я сейчас и занимаюсь.
Коммерческие системы плохи тем что они 1) коммерческие и 2) их не особо приятно указывать в ссылках, списке литературы etc.
Это все в рамках дипломной работы, так что пользоваться коммерческими продуктами тяжело - обычно они не спешат делиться потрохами, которые мне необходимо не только понимать, но и вероятно описывать в той или иной мере. А вот открытые удобны для этого. Сейчас пробую прикрутить OpenOpt + SciPy.
Надеюсь, мое и Ваше соображения помогут еще кому, кто столкнется с подобной задачей.
Если будут еще мысли -- с удовольствием почитаю.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 3 ] 

Модераторы: maxal, Toucan, PAV, Karan, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group