Часто в Интернете попадаются научные публикации, в которых авторы сообщают о своих работ в области совершенствования т.наз. методов "внутренной точки" (по англ.: "interior point") для решения важных классов нелинейного программирования. Для задач линейного программирования тоже, можно, как говорят, с релаксацией, т.е. с отказом от требования линейности, видоизменить целевой функции, так, чтобы она стала нелинейной: стремясь к бесконечности при приближении из внутри к оболочке многостена линейных ограничений. Это помогает по меньшей мере: методами внутренной точки приблизится изнутри к той части многостена, где находится оптимальная его вершина. Быстро переплававь внутренность его, вместо симплексным методом долго зиг-загить по поверхности многостена.
Говорю вот почему. Пока никто Вам не указывает на набор тестовых задач, не попробовать ли Вам например решить Вашим пакетом программ, если о том идет речь, хорошо изведанный набор задач
линейного программирования с большими размерами, с известным наперед оптимальным решением, или с ответом, что нет вообще решения. На примере этого набора в последные годы и понастоящем многие Ваши коллеги в мире проверяют на быстродействие и вообще на эффективность море улучшений алгоритмов и программ и сообщают в своих публикациях о результатах?
Верно, что они линейные. Верно, что для таких задач есть и гораздо более эффективные или более прямые методы решения.
И все таки, я бы на вашем месте, проверил бы свой софтуер сначала и на линейных задачах, о которых можно почитать по линку:
http://www.netlib.org/lp/data/readme
