Решение проблемы упаковки контейнеров с помощью Perl и NEOS Server

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

Здесь мы демонстрируем использование языка программирования Perl для моделирования и решения небольшого экземпляра задачи упаковки контейнеров, используя CPLEX в качестве решателя, с помощью службы NEOS Server.

NEOS Server — это бесплатный интернет-сервис для решения задач численной оптимизации. Расположенный в Висконсинском институте открытий при Висконсинском университете в Мэдисоне, NEOS Server предоставляет доступ к более чем 60 современным решателям в более чем дюжине категорий оптимизации. Решатели, размещенные в Висконсинском университете в Мэдисоне, работают на распределенных высокопроизводительных машинах с программным обеспечением HTCondor; удаленные решатели работают на машинах в Университете штата Аризона, Университете Клагенфурта в Австрии и Университете Миньо в Португалии. Источник: Веб-сайт NEOS Server

Сервер NEOS и Perl

Насколько мне известно, для NEOS Server не существует модуля или интерфейса на языке Perl, но поскольку есть возможность взаимодействовать с NEOS Server с помощью XML-RPC, ниже приведена функция, разработанная для отправки оптимизационных задач:

sub solve_model_using_neos
{
    my $xml_job = $_[0];
    my $neos = XML::RPC->new('https://neos-server.org:3333');

    my $alive = $neos->call( 'ping', );
    die "Error: Neos Server not available!" if $alive !~ "NeosServer is alive";

    # submit job for solution
    my ($job_number, $job_pwd) = @{ $neos->call('submitJob', $xml_job) };

    # Get the job status
    my $job_status = $neos->call('getJobStatus', ($job_number, $job_pwd));
    print "Status: $job_statusn";

    # Possible status: "Done", "Running", "Waiting", "Unknown Job", or "Bad Password"
    my @valid_status = ('Done', 'Unknown Job', 'Bad Password');
    while (not grep( /^$job_status$/, @valid_status ) ) 
    {
        $job_status = $neos->call('getJobStatus', ($job_number, $job_pwd));
        print "Job: $job_number => status: $job_statusn";
    }

    return ($job_number, $job_pwd, $job_status);
}
Вход в полноэкранный режим Выход из полноэкранного режима

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

Более подробно с синтаксисом можно ознакомиться в веб-интерфейсе NEOS Server, где также можно сделать «сухой прогон» и сгенерировать только xml-файл для анализа.

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

Пример модели

# Given a set of items I = {1,...,m} with weight w[i] > 0, 
# the Bin Packing Problem (BPP) is to pack the items into 
# bins of capacity c in such a way that the number of bins 
# used is minimal.
#
# Extracted from GLPK distribution (https://www.gnu.org/software/glpk/)
# Inspired in GNU MathProg version developed by Andrew Makhorin <mao@gnu.org>
sub generate_bin_packing_problem
{
    my $c = 100; # capacity of each bin
    my $m = 6;   # number of items to pack (6 items)

    # weight of each item.
    my %w = (1 => 50, 2 => 60, 3 => 30, 4 => 70, 5 => 50, 6 => 40);

    # - "greedy" estimation of the upper bound in terms of 
    # the number of bins needed
    my $accum = 0;
    my $n = 1; # upper bound of the number of bins needed.
    foreach my $item (keys %w)
    {
        if($accum + $w{$item} > $c)
        {
            $accum = $w{$item};
            $n++;
        } else {
            $accum += $w{$item};
        }
    }

    # Create objective function
    # Minimize the number of used bins
    my $model = "Minimizen";
    $model .= " obj:";
    for(1..$n)
    {
        $model .= " + used($_)";
    }
    $model .= "n";
    $model .= "Subject Ton";

    # Each item must be inserted in one bin
    for(my $item = 1; $item <= $m; $item++)
    {
        $model .= " one($item):";
        for(my $bin = 1; $bin <= $n; $bin++)
        {
            $model .= " + x($item,$bin)";
        }
        $model .= " = 1n";
    }

    # Constraint:
    # Respect the capacity of each bin, i.e., the sum of
    # the weight put in each bin must be lower than or 
    # equal to the bin capacity.
    for(my $bin = 1; $bin <= $n; $bin++)
    {
        $model .= " lim($bin):";
        for(my $item = 1; $item <= $m; $item++)
        {
            $model .= " + $w{$item} x($item,$bin)";
        }
        $model .= " - $c used($bin) <= 0n";
    }

    # Constraint:
    # Define the bounds for each variable, in this case, 
    # all variables are binary, with lower bound equals 
    # to 0 and upper bound equals to 1.
    $model .= "nBoundsn";
    for(my $bin = 1; $bin <= $n; $bin++)
    {
        $model .= " 0 <= used($bin) <= 1n";
        for(my $item = 1; $item <= $m; $item++)
        {
            $model .= " 0 <= x($item,$bin) <= 1n";
        }
    }

    # Constraint:
    # Explicitly say to the solvers that the variables 
    # are integers, i.e., no factional value is allowed.
    $model .= "nGeneralsn";
    for(my $bin = 1; $bin <= $n; $bin++)
    {
        $model .= " used($bin)n";
        for(my $item = 1; $item <= $m; $item++)
        {
            $model .= " x($item,$bin)n";
        }
    }

    return $model;
}
Вход в полноэкранный режим Выйти из полноэкранного режима

Весь код состоит примерно из 200 строк и доступен в этом репозитории github.

Вкратце, этот код: (i) генерирует задачу оптимизации, (ii) создает xml-строку для отправки в NEOS Server, (iii) загружает журнал CPLEX и результаты, (iv) разбирает полученный результат в формате XML и выводит в консоль значения переменных вместе со статусом, возвращенным CPLEX.

Оцените статью
devanswers.ru
Добавить комментарий