Познакомить вас с двумя методами линейного программирования: хранением разреженных матриц и предварительной обработкой.

Аннотация: В этой статье рассказывается о хранении разреженных матриц и предварительной обработке данных для линейного программирования.

Эта статья опубликована в сообществе HUAWEI CLOUD.«Линейное программирование — разреженная матрица», оригинальный автор: Bale10.

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

разреженная матрица

Размер LP обычно определяется размером матрицы ограничений A. Элементы матрицы обычно хранятся в 8-байтовом типе double.Предполагая, что матрица имеет m строк и n столбцов, для непосредственного хранения A требуется 8 млн байтов. . Если A имеет 10 000 строк и 20 000 столбцов (не особо масштабно), то для хранения A требуется 1,6G памяти. С одной стороны, требования к памяти высоки, а с другой стороны, работа с матрицей A затруднена . Крупномасштабная ЛП обычно содержит большое количество нулевых элементов, а доля ненулевых элементов очень мала Это свойство называется разреженностью, то есть А является разреженной матрицей.

Хранение разреженных матриц

При проектировании структуры данных разреженной матрицы следует учитывать следующие три фактора:

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

2. Генерация ненулевых элементов - элементов заполнения, разреженной матрицы, в процессе исключения Гаусса (или LU разложения) исходные нулевые элементы могут стать ненулевыми элементами. В процессе исключения ненулевой элемент, который заменяется нулевым элементом, называется элементом заполнения; количество элементов заполнения, сгенерированных в течение всего процесса исключения, называется количеством заполнения. Если очень разреженная матрица генерирует большое количество заполняющих элементов после указанной выше операции исключения, разреженность исчезнет.Поэтому сохранение разреженности матрицы является предпосылкой использования ее разреженности. Как попытаться сгенерировать как можно меньше заполняющих элементов в процессе исключения — это алгоритм, который необходимо учитывать. Разреженная матрица — это динамическая структура данных, в частности, часто бывает необходимо вставлять ненулевые элементы или удалять ненулевые элементы. Следовательно, хорошая разреженная матричная структура данных должна облегчать вставку или удаление.

3. Структура данных разреженной матрицы тесно связана с алгоритмом исключения.При рассмотрении структуры данных разреженной матрицы одновременно необходимо учитывать алгоритм исключения, а структура данных должна быть максимально удобной реализовать алгоритм.

Линейный стол

Простейшей схемой хранения разреженных матриц является линейная таблица. Для конкретности возьмем в качестве примера следующую разреженную матрицу A_5:

Сохраняйте ненулевые записи в массиве CE по столбцам:

Номер строки соответствующего ненулевого элемента в CE записывается в массив IROW:

Чтобы указать номер столбца каждого ненулевого элемента, вводится массив указателей ICFR, а ICFR(j) представляет позицию первого ненулевого элемента в j-м столбце в CE.

Длина ICFR равна N+1, ICFR(N+1) означает, что последний элемент хранится в $N$ Добавьте 1 к позиции последнего элемента столбца, что введено для облегчения подсчета количества ненулевых элементов в последнем столбце. Объем хранилища, необходимый для этой схемы хранения, составляет 2NZ+N+1. Он имеет преимущества небольшого объема памяти и простой структуры.Единственным недостатком является то, что его неудобно вставлять и удалять.Чтобы вставить ненулевой элемент, ненулевой элемент под ним должен быть перемещен вниз на позицию, что очень время -потребление.

Чтобы разрешить вставку ненулевых элементов в программу, обычно необходимо указать больший массив. Вышеупомянутое предназначено для хранения A в столбцах, конечно, его также можно хранить в строках. Обычная практика заключается в том, чтобы сначала выполнить LU-разложение A, а затем сохранить нижнюю треугольную матрицу L в столбцах и верхнюю треугольную матрицу U в строках.

Единый список

Чтобы преодолеть недостатки линейных списков, которые нелегко вставлять и удалять, вводится структура данных связанного списка. То есть массив указателей связанного списка LNXT добавляется к приведенной выше линейной таблице, LNXT(i) представляет позицию следующего ненулевого элемента i-го ненулевого элемента, а массив ICNZ используется для записи количество ненулевых элементов в столбце. Этот связанный список называется односвязным списком, также известным как связанный список столбцов. По-прежнему возьмите приведенную выше разреженную матрицу A_5 в качестве примера и сохраните ее в столбцах:

Из приведенной выше структуры таблицы видно, что для каждого ненулевого элемента разреженной матрицы в таблице имеется тройка (номер строки, элемент, позиция следующего элемента), а именно

Каждый столбец ненулевых элементов представлен цепным указателем $LNXT$ Связанный, последний ненулевой элемент каждого столбца, указатель цепочки равен 0, что указывает на конец цепочки. а массив указателей $ICFR$ Указывает положение заголовка каждого столбца.

1. Ненулевые элементы в одном столбце не обязательно хранить рядом друг с другом, потому что используется каждый ненулевой элемент $LNXT$ Указывает расположение следующего элемента, поэтому следующий элемент можно разместить в любом месте таблицы.

2. Вставьте и удалите элемент, не перемещая другие элементы, просто меняя указатель.

Преимущество использования связанного списка заключается в том, что его легко вставлять или удалять; недостатком является то, что доступ к любому элементу в связанном списке необходимо искать последовательно, начиная с первого ненулевого элемента столбца, и оба требуют косвенного доступа. поэтому это медленнее, чем доступ к линейному списку.

двусвязный список

Двусвязный список основан на односвязном списке путем добавления номера столбца i-го ненулевого элемента ICOL(i), указателя цепочки строк i-го ненулевого элемента RNXT(i) , то есть положение следующего ненулевого элемента строки, и IRFR(i) положение первого ненулевого элемента строки i в связанном списке.

Эта структура данных двусвязного списка очень удобна для работы с разреженными матрицами с асимметричной структурой и имеет преимущества односвязного списка, то есть вставку и удаление.

Операция вставки или удаления элемента в двусвязном списке такая же, как и в односвязном списке, только обратите внимание, что вставка или удаление элемента не только изменяет цепочку столбцов и цепочку пустых ячеек, но также изменяет строку цепь.

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

предварительная обработка данных

Масштабы задач линейного программирования становятся все больше и больше Задачи с тысячами ограничений и переменных очень распространены, и они сталкиваются с проблемой хранения данных и эффективности обработки Крупномасштабные задачи обычно автоматически генерируются инструментами поддержки моделей, и их часто являются проблемами.При большом количестве избыточных ограничений и переменных необходима предварительная обработка данных перед решением алгоритма.

Главная цель

1. Уменьшить избыточные ограничения, уменьшить ненулевые элементы матрицы ограничений, улучшить разреженность, уменьшить масштаб проблемы и сэкономить память;

2. Улучшить числовые характеристики модели и повысить численную устойчивость задачи;

3. Решите, что проблема не имеет допустимого решения или является неограниченной, не решая проблему.