Perl 및 NEOS 서버를 사용하여 Bin Packing 문제 해결

빈 패킹 문제는 최적화 문제로, 다양한 크기의 항목을 제한된 수의 빈 또는 컨테이너에 각각 고정된 주어진 용량을 사용하여 사용되는 빈 수를 최소화하는 방식으로 포장해야 합니다. 이 문제는 컨테이너 채우기, 중량 제한이 있는 트럭 적재, 미디어에서 파일 백업 생성, FPGA 반도체 칩 설계에서 기술 매핑과 같은 많은 응용 분야에 적용됩니다. 출처: Wikipedia

여기서는 Perl 프로그래밍 언어를 사용하여 NEOS 서버 서비스를 통해 CPLEX을 솔버 엔진으로 사용하여 빈 패킹 문제의 작은 인스턴스를 모델링하고 해결하는 방법을 보여줍니다.

NEOS 서버는 수치 최적화 문제를 해결하기 위한 무료 인터넷 기반 서비스입니다. 매디슨 소재 위스콘신 대학교의 Wisconsin Institute for Discovery에서 호스팅하는 NEOS 서버는 12개 이상의 최적화 범주에서 60개 이상의 최첨단 솔버에 대한 액세스를 제공합니다. 매디슨에 있는 위스콘신 대학교에서 호스팅하는 솔버는 HTCondor 소프트웨어로 지원되는 분산 고성능 시스템에서 실행됩니다. 원격 솔버는 애리조나 주립 대학, 오스트리아의 클라겐푸르트 대학, 포르투갈의 미뉴 대학의 기계에서 실행됩니다. 출처: NEOS Server website

NEOS 서버 및 Perl

내가 아는 한 Perl에는 NEOS 서버에 사용할 수 있는 모듈이나 인터페이스가 없지만 XML-RPC를 사용하여 NEOS 서버에 인터페이스할 수 있으므로 최적화 문제를 제출하기 위해 개발된 함수 아래에 있습니다.

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_status\n";

    # 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_status\n";
    }

    return ($job_number, $job_pwd, $job_status);
}

이 함수는 모델과 함께 전달될 수 있는 일부 매개변수가 포함된 xml 문자열을 인수로 수신하고 작업 ID, 암호 및 제출 상태를 반환합니다. 예를 들어 결과 다운로드와 같은 모든 후속 작업에는 작업 ID와 암호가 필요합니다.

구문에 대한 자세한 내용은 NEOS Server web interface에서 볼 수 있습니다. 여기에서 "테스트 실행"을 수행하고 분석을 위해 xml 파일만 생성할 수도 있습니다.

모델 자체는 CPLEX LP 파일 형식으로 개발되었습니다. 즉, 모델의 일부인 목적 함수 및 제약 조건과 같은 수학 방정식을 직접 작성할 수 있는 간단한 텍스트 파일입니다. CPLEX LP 파일 형식을 작성하는 규칙은 예를 들어 this link 에서 볼 수 있습니다.

예제 모델

# 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 <[email protected]>
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 = "Minimize\n";
    $model .= " obj:";
    for(1..$n)
    {
        $model .= " + used($_)";
    }
    $model .= "\n";
    $model .= "Subject To\n";

    # 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 .= " = 1\n";
    }

    # 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) <= 0\n";
    }

    # 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 .= "\nBounds\n";
    for(my $bin = 1; $bin <= $n; $bin++)
    {
        $model .= " 0 <= used($bin) <= 1\n";
        for(my $item = 1; $item <= $m; $item++)
        {
            $model .= " 0 <= x($item,$bin) <= 1\n";
        }
    }

    # Constraint:
    # Explicitly say to the solvers that the variables 
    # are integers, i.e., no factional value is allowed.
    $model .= "\nGenerals\n";
    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줄이 있으며 this github 저장소에서 사용할 수 있습니다.

요약하면 이 코드는 (i) 최적화 문제를 생성하고, (ii) NEOS 서버에 제출할 xml 문자열을 생성하고, (iii) CPLEX 로그 및 결과를 다운로드하고, (iv) XML 형식으로 얻은 결과를 구문 분석하고 인쇄합니다. 콘솔에서 CPLEX가 리턴한 상태와 함께 변수의 값.