/go-glpk

Go bindings for GLPK (GNU Linear Programming Kit)

Primary LanguageGoGNU General Public License v3.0GPL-3.0

glpk

Package glpk contains Go bindings for GLPK (GNU Linear Programming Kit).

The binding is not complete but enough for my purposes. Fill free to contact me (email at the end) if there is some part of GLPK that you would like to use and it is not yet covered by the glpk package.

Package glpk is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.

Instalation

First install GLPK (GNU Linear Programming Kit). Package glpk is known to work with GLPK v4.54 (available in Debian Sid) and v4.45 (available in Debian Wheezy). On Debian GLPK can be installed by installing the package libglpk-dev.

To install glpk package run

go get github.com/lukpank/go-glpk/glpk

Documentation

Documentation for glpk package is available on godoc.org.

Examples

Example with real-valued variables

This example is a Go rewrite of the PyGLPK example from http://tfinley.net/software/pyglpk/discussion.html (Which is a Python reimplementation of a C program from GLPK documentation).

package main

import "fmt"
import "github.com/lukpank/go-glpk/glpk"

func main() {
	lp := glpk.New()
	lp.SetProbName("sample")
	lp.SetObjName("Z")
	lp.SetObjDir(glpk.MAX)

	lp.AddRows(3)
	for i := 0; i < 3; i++ {
		name := fmt.Sprintf("%c", 'p'+i)
		lp.SetRowName(i+1, name)
	}
	lp.SetRowBnds(1, glpk.UP, 0, 100.0)
	lp.SetRowBnds(2, glpk.UP, 0, 600.0)
	lp.SetRowBnds(3, glpk.UP, 0, 300.0)

	lp.AddCols(3)
	for i := 0; i < 3; i++ {
		name := fmt.Sprintf("x%d", i)
		lp.SetColName(i+1, name)
		lp.SetColBnds(i+1, glpk.LO, 0.0, 0.0)
	}

	lp.SetObjCoef(1, 10.0)
	lp.SetObjCoef(2, 6.0)
	lp.SetObjCoef(3, 4.0)

	ind := []int32{0, 1, 2, 3}
	mat := [][]float64{
		{0, 1.0, 1.0, 1.0},
		{0, 10.0, 4.0, 5.0},
		{0, 2.0, 2.0, 6.0}}
	for i := 0; i < 3; i++ {
		lp.SetMatRow(i+1, ind, mat[i])
	}

	lp.Simplex(nil)

	fmt.Printf("%s = %g", lp.ObjName(), lp.ObjVal())
	for i := 0; i < 3; i++ {
		fmt.Printf("; %s = %g", lp.ColName(i+1), lp.ColPrim(i+1))
	}
	fmt.Println()

	lp.Delete()
}

The output of this example is:

GLPK Simplex Optimizer, v4.54
3 rows, 3 columns, 9 non-zeros
*     0: obj =   0.000000000e+00  infeas =  0.000e+00 (0)
*     2: obj =   7.333333333e+02  infeas =  0.000e+00 (0)
OPTIMAL LP SOLUTION FOUND
Z = 733.3333333333333; x0 = 33.333333333333336; x1 = 66.66666666666666; x2 = 0

Reading the problem instance from a file

The above problem in the CPLEX LP format has the follow form

\* Problem: sample *\

Maximize
 Z: + 10 x0 + 6 x1 + 4 x2

Subject To
 p: + x2 + x1 + x0 <= 100
 q: + 5 x2 + 4 x1 + 10 x0 <= 600
 r: + 6 x2 + 2 x1 + 2 x0 <= 300

End

let us save it into sample.lp file. Then we can do the computation analogous to the previous example with the following shorter program:

package main

import (
	"fmt"
	"log"

	"github.com/lukpank/go-glpk/glpk"
)

func main() {
	lp := glpk.New()
	defer lp.Delete()
	lp.ReadLP(nil, "sample.lp")

	if err := lp.Simplex(nil); err != nil {
		log.Fatal(err)
	}

	fmt.Printf("%s = %g", lp.ObjName(), lp.ObjVal())
	for i := 0; i < 3; i++ {
		fmt.Printf("; %s = %g", lp.ColName(i+1), lp.ColPrim(i+1))
	}
	fmt.Println()
}

Analogously you can read from a file in MPS or GPLK LP/MIP formats using ReadMPS or ReadProb methods. You can also write the problem instance in MPS, CPLEX LP or GPLK LP/MIP formats by the corresponding WriteMPS, WriteLP and WriteProb methods.

The output of this example is:

Reading problem data from 'sample.lp'...
3 rows, 3 columns, 9 non-zeros
11 lines were read
GLPK Simplex Optimizer, v4.55
3 rows, 3 columns, 9 non-zeros
*     0: obj =   0.000000000e+00  infeas =  0.000e+00 (0)
*     2: obj =   7.333333333e+02  infeas =  0.000e+00 (0)
OPTIMAL LP SOLUTION FOUND
Z = 733.3333333333333; x0 = 33.333333333333336; x1 = 66.66666666666666; x2 = 0

MIP (Mixed Integer Programming) example

This example is a Go rewrite of the glpk MIP (Mixed Integer Programming) example written by Masahiro Sakai. See glpk-mip-sample.c.

package main

import (
	"fmt"
	"log"

	"github.com/lukpank/go-glpk/glpk"
)

// Maximize
//
//      obj: x1 + 2 x2 + 3 x3 + x4
//
// Subject To
//
//      c1: 0 <= - x1 + x2 + x3 + 10 x4 <= 20
//      c2: 0 <= x1 - 3 x2 + x3 <= 30
//      c3: x2 - 3.5 x4 = 0
//
// Bounds
//
//      0 <= x1 <= 40
//      x2 >= 0
//      x3 >= 0
//      2 <= x4 <= 3
//
// Type
//
//      x1, x2, x3 real
//      x4 integer
//
// End
func main() {
	lp := glpk.New()
	lp.SetProbName("sample")
	lp.SetObjName("Z")
	lp.SetObjDir(glpk.MAX)

	lp.AddRows(3)
	lp.SetRowName(1, "c1")
	lp.SetRowBnds(1, glpk.UP, 0.0, 20.0)
	lp.SetRowName(2, "c2")
	lp.SetRowBnds(2, glpk.UP, 0.0, 30.0)
	lp.SetRowName(3, "c3")
	lp.SetRowBnds(3, glpk.FX, 0.0, 0)

	lp.AddCols(4)
	lp.SetColName(1, "x1")
	lp.SetColBnds(1, glpk.DB, 0.0, 40.0)
	lp.SetObjCoef(1, 1.0)
	lp.SetColName(2, "x2")
	lp.SetColBnds(2, glpk.LO, 0.0, 0.0)
	lp.SetObjCoef(2, 2.0)
	lp.SetColName(3, "x3")
	lp.SetColBnds(3, glpk.LO, 0.0, 0.0)
	lp.SetObjCoef(3, 3.0)
	lp.SetColName(4, "x4")
	lp.SetColBnds(4, glpk.DB, 2.0, 3.0)
	lp.SetObjCoef(4, 1.0)
	lp.SetColKind(4, glpk.IV)

	fmt.Printf("col1: %v\n", lp.ColKind(1) == glpk.CV)

	ind := []int32{0, 1, 2, 3, 4}
	mat := [][]float64{
		{0, -1, 1.0, 1.0, 10},
		{0, 1.0, -3.0, 1.0, 0.0},
		{0, 0.0, 1.0, 0.0, -3.5}}
	for i := 0; i < 3; i++ {
		lp.SetMatRow(i+1, ind, mat[i])
	}

	iocp := glpk.NewIocp()
	iocp.SetPresolve(true)

	if err := lp.Intopt(iocp); err != nil {
		log.Fatalf("Mip error: %v", err)
	}

	fmt.Printf("%s = %g", lp.ObjName(), lp.MipObjVal())
	for i := 0; i < 4; i++ {
		fmt.Printf("; %s = %g", lp.ColName(i+1), lp.MipColVal(i+1))
	}
	fmt.Println()

	lp.Delete()
}

The output of this example is:

GLPK Integer Optimizer, v4.55
3 rows, 4 columns, 9 non-zeros
1 integer variable, none of which are binary
Preprocessing...
3 rows, 4 columns, 9 non-zeros
1 integer variable, none of which are binary
Scaling...
 A: min|aij| =  1.000e+00  max|aij| =  1.000e+01  ratio =  1.000e+01
Problem data seem to be well scaled
Constructing initial basis...
Size of triangular part is 3
Solving LP relaxation...
GLPK Simplex Optimizer, v4.55
3 rows, 4 columns, 9 non-zeros
      0: obj =   2.300000000e+01  infeas =  1.400e+01 (0)
*     1: obj =   3.700000000e+01  infeas =  0.000e+00 (0)
*     5: obj =   1.252083333e+02  infeas =  0.000e+00 (0)
OPTIMAL LP SOLUTION FOUND
Integer optimization begins...
+     5: mip =     not found yet <=              +inf        (1; 0)
+     6: >>>>>   1.225000000e+02 <=   1.225000000e+02 < 0.1% (2; 0)
+     6: mip =   1.225000000e+02 <=     tree is empty   0.0% (0; 3)
INTEGER OPTIMAL SOLUTION FOUND
Z = 122.5; x1 = 40; x2 = 10.5; x3 = 19.5; x4 = 3

About

Package glpk was written by Łukasz Pankowski (username at o2 dot pl; where username is lukpank).