Одномерная задача раскроя

[eugrita]

Эта задача как понимаю, впервые поставленная Канторовичем и его школой изучается естественно в приличных ВУЗах
Однако в весьма куцем виде. Варианты постановок -а) мин количества заготовок б)мин отходов при обеспечении заданных объемов поставок
Для сведения ее к стандартной задаче линейного программирования и применения симплекс-метода надо еще решить подзадачу - найти оптимальные. векторы вариантов раскроя. Оптимальные в смысле Парето т.е чтобы при сравнении любых двух не было бы чтобы все компоненты одного меньше всех компонент другого.
Эта часть задачи обычно проглатывается - и это понятно - кому охота заниматься в ВУЗе программированием если
задачу ЛП при известной матрице можно решить в Excel с помощью налстройки Поиск решения
Я восполнил недостающую часть алгоритма- построение набора векторов Парето и вместе с ними матрицы
задачи линейного программирования 1-мерного раскроя
Пусть $L_s$ длина заготовки $n$ -кол-во типов кусков (разные длины
$L_i$ - массив длин кусков
Задача ставится по известным входным данным найти количество $kp$ и набор векторов Парето
$\bar{x}$ и матрицу $A$ задачи ЛП. (столбцы которой составлены из этих векторов)
Эта задача мной решена, т.е. написана программа делающая это.
Но результаты все же удручают. Так если при количестве типов заготовок $n=3$
и не очень больших длинах скажем $L_s=13$ получается набор из 7 векторов (матрица 3x7) то уже при
$n=5 $ и $L_s=24$ получается 59 векторов и матрица 5x59
Конечно и такую матрицу можно запихнуть в симплекс-метод и получить оптимальное решение, но ясно что здесь висит проблема размерности.
Пример расчета
$n=3$ $L_s=13$ $L_=(3,4,5)
\qquad \begin{Vmatrix} 0 & 0 & 0 & 1 & 1 &1 & 2 \\ 1 & 2 & 3 & 0 & 1 &2 & 0 \\ 3 & 1 & 0 & 2 & 1 & 0 & 1 \end{Vmatrix} $
Вопрос - как повысить эффективность алгоритма решения задачи одномерного раскроя
без перехода к параллельным вычислениям?