View on GitHub

PDL::Opt::GLPK

an interface to GLPK

NAME

PDL::Opt::GLPK - PDL interface to the GNU Linear Programming Kit

SYNOPSIS

    use PDL;
    use PDL::Opt::GLPK;

    glpk($c, $a, $b $lb, $ub, $ctype, $vtype, GLP_MAX,
           $xopt = null, $fopt = null, $status = null,
           $lambda = null, $redcosts = null, \%param);

DESCRIPTION

This module provides an interface to GLPK, the GNU Linear Programming Kit. The interface was ported from Octave and mimics its GLPK interface.

FUNCTIONS

glpk

Signature (c(m); a(m, n); b(n); lb(m); ub(m); ctype(n); vtype(m);
       int sense; [o]xopt(m); [o]fopt(); [o]status(); [o]lambda(n);
       [o]redcosts(n); SV *param)

Solve a linear program using the GNU GLPK library.

The LP can be of the form

    [ min | max ] C'*x
    subject to

    A*x [ "=" | "<=" | ">=" ] b
      x >= LB
      x <= UB

Arguments

Input values:

Output values:

EXAMPLES

A standard case

A modified example from the GLPK documentation, with an extra variable to avoid a square matrix:

    Maximize
     obj: + 10 x_1 + 6 x_2 + 4 x_3 - x_4

    Subject To
     r_1: + x_1 + x_2 + x_3 + x_4 <= 100
     r_2: + 10 x_1 + 4 x_2 + 5 x_3 + x_4 <= 600
     r_3: + 2 x_1 + 2 x_2 + 6 x_3 + x_4 <= 300

The solution is straightforward:

use PDL;
use PDL::Opt::GLPK;

$a = pdl([[1, 1, 1, 1], [10, 4, 5, 1], [2, 2, 6, 1]]);
$b = pdl([100, 600, 300]);
$c = pdl([10, 6, 4, -1]);
$lb = zeroes(4);
$ub = inf(4);
$ctype = pdl([GLP_UP, GLP_UP, GLP_UP]);
$vtype = pdl([GLP_CV, GLP_CV, GLP_CV, GLP_CV]);

glpk($c, $a, $b $lb, $ub, $ctype, $vtype, GLPX_MAX,
   $xopt = null, $fopt = null, $status = null);

# $xopt:
# [
#   [ 33.333333  66.666667      0          0]
# ]

# $fopt:
# [ 733.33333]

Broadcasting

Multiple problems on the same coefficients may be solved simultaneously. Some care must be taken when all combinations of multiple arguments are requested.

The base problem:

    Maximize
     obj: + y_1 + y_2 + y_3 + y_4

    Subject To
     r_1: - y_2 + y_1 >= 1
     r_2: - y_3 + y_2 >= 1
     r_3: - y_4 + y_3 >= 1

    Bounds
     0 <= y_1 <= 4
     0 <= y_2 <= 4
     0 <= y_3 <= 4
     0 <= y_4 <= 4

    Generals
     y_1
     y_2
     y_3
     y_4

Looking for the objective function’s minimum and maximum with both lower and upper bound constraints:

use PDL;
use PDL::Opt::GLPK;

my $a = pdl(
    [[1, -1, 0, 0],
     [0, 1, -1, 0],
     [0, 0, 1, -1]]);
my $b = pdl([1, 1, 1]);
my $c = pdl([1, 1, 1, 1]);
my $lb = pdl([0, 0, 0, 0]);
my $ub = pdl([4, 4, 4, 4]);

# dims: 3, 2 - loop over lower and upper bounds
my $ctype = pdl([[GLP_LO, GLP_LO, GLP_LO],[GLP_UP, GLP_UP, GLP_UP]]);

my $vtype = (GLP_IV * ones(4));

# dims: 1, 2 - extra loop over min and max
my $sense = pdl [[GLPX_MAX], [GLPX_MIN]];

my $xopt = null;
my $fopt = null;
my $status = null;

glpk($c, $a, $b, $lb, $ub, $ctype, $vtype, $sense, $xopt, $fopt, $status);

# $xopt:
# [
#  [
#   [4 3 2 1]
#   [4 4 4 4]
#  ]
#  [
#   [3 2 1 0]
#   [0 0 0 0]
#  ]
# ]
#
# $fopt:
# [
#  [10 16]
#  [ 6  0]
# ]

Specifying parameters

The params hash ref is always the last argument. It is permitted to leave out the other optional output arguments, as in

    glpk($c, $a, $b, $lb, $up, $ctpye, $vtype, $sense,
        $xopt, $fopt, $status, {save_pb => 1});

ERRORS

In case the solver reports an error, it will raise an PDL error.

AUTHOR

Jörg Sommrey

COPYRIGHT AND LICENSE

Copyright 2024 Jörg Sommrey

This library is free software; you may redistribute it and/or modify it under the terms of the GNU GENERAL PUBLIC LICENSE Version 3. See COPYING.

SEE ALSO

The Octave Manual: https://docs.octave.org/latest/Linear-Programming.html

The GNU Linear Programming Kit: https://www.gnu.org/software/glpk/

The GLPK reference manual is included in the GLPK distribution.