Solving Bin Packing Problem using Perl and NEOS Server

The bin packing problem is an optimization problem, in which items of different sizes must be packed into a finite number of bins or containers, each of a fixed given capacity, in a way that minimizes the number of bins used. The problem has many applications, such as filling up containers, loading trucks with weight capacity constraints, creating file backups in media and technology mapping in FPGA semiconductor chip design. Source: Wikipedia

Here we demonstrate the use of Perl programming language to model and solve a small instance of the bin packing problem using CPLEX as a solver engine, via NEOS Server service.

The NEOS Server is a free internet-based service for solving numerical optimisation problems. Hosted by the Wisconsin Institute for Discovery at the University of Wisconsin in Madison, the NEOS Server provides access to more than 60 state-of-the-art solvers in more than a dozen optimisation categories. Solvers hosted by the University of Wisconsin in Madison run on distributed high-performance machines enabled by the HTCondor software; remote solvers run on machines at Arizona State University, the University of Klagenfurt in Austria, and the University of Minho in Portugal. Source: NEOS Server website

NEOS Server and Perl

To the best of my knowledge, there is no module or interface available for NEOS Server in Perl, but since it's possible to interface NEOS Server using XML-RPC, below the function developed to submit optimisation problems:

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);
}

This function receives as an argument a xml string with some parameters that can be passed together with the model, and returns the job id, password and the status of the submission. The job id and password are necessary for all subsequent operations, such as, downloading the results for example.

More details about the syntax can be seen in the NEOS Server web interface, where it's possible also to do a "dry run" and generate only the xml file for analysis.

The model itself was developed in CPLEX LP file format, that is a simple text file where you can write mathematical equations directly, such as the objective function and constraints that are part of the model. The rules to create a CPLEX LP file format can be seen for example in this link.

Example model

# 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 <[e-mail]>
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;
}

The entire code has around 200 lines and is available in this github repository.

To summarise, this code: (i) generates the optimization problem, (ii) create the xml string for submission in NEOS Server, (iii) download CPLEX log and the results, (iv) parse the result obtained in XML format, and print in console the value of the variables together with the status returned by CPLEX.