Package glpk

This article is about a function from ApCoCoA-2. If you are looking for the ApCoCoA-1 version of it, see Category:ApCoCoA-1:Package glpk.

This page describes the glpk package. For a complete list of functions, see Category:Package glpk.

The basic idea behind this package is to make the linear optimization program GLPK usable in/with ApCoCoA. The package GLPK contains various functions that let you make use of the GLPK library, rather the stand-alone LP/MIP Solver glpsol.

Important: For usage under linux, the GLPK-Program glpsol must be in the ApCoCoA package directory under packages/binaries/glpk/examples/glpsol and you must have the permissions to read and write in this directory. For Windows, the glsol.exe has to be in the folder \packages\binaries\glpk\w64\glpsol.exe. If you installed ApCoCoA-2 together with the GUI, this should already be the case.

The source code of GLPK can be downloaded at [1].

Optimizing Linear Systems Of Equations

See also: GLPK.LPSolve

Let $n\in \mathbb {N}$ and $P=\mathbb {Q} [x_{1},\ldots ,x_{n}]$. Let $f_{1},\ldots ,f_{s_{1}},g_{1},\ldots ,g_{s_{2}},h_{1},\ldots ,h_{s_{3}},c\in P$ be linear polynomials and let $l_{1},\ldots ,l_{n},u_{1},\ldots ,u_{n}\in \mathbb {Q} \cup \{-\infty ,\infty \}$. Let $S$ be the system of polynomial (in)equations

$\left\{{\begin{array}{ccc}f_{1}(b)&=&0\\\vdots &\vdots &\vdots \\f_{s_{1}}(b)&=&0\\g_{1}(b)&\leq &0\\\vdots &\vdots &\vdots \\g_{s_{2}}(b)&\leq &0\\h_{1}(b)&\geq &0\\\vdots &\vdots &\vdots \\h_{s_{3}}(b)&\geq &0.\end{array}}\right.$

Then the function GLPK.LPSolve can be used to find solution $b\in [l_{1},u_{1}]\times \cdots \times [l_{n},u_{n}]$ to $S$ such that $c(b)=\min\{c(x)\mid x\in [l_{1},u_{1}]\times \cdots \times [l_{n},u_{n}]{\text{ is a solution to }}S\}$ in the following way.

• Let EQ be the list $\{f_{1},\ldots ,f_{s_{1}}\}$, let LE be the list $\{g_{1},\ldots ,g_{s_{2}}\}$, and let GE be the list $\{h_{1},\ldots ,h_{s_{3}}\}$.
• Let l and u be lists with l[i]$=l_{i}$ if $l_{i}\in \mathbb {Q}$ (resp. u[i]$=u_{i}$ if $u_{i}\in \mathbb {Q}$) and l[i] = "" if $l_{i}=-\infty$ (resp. u[i] = "" if $u_{i}=\infty$). Furthermore, we set B := [ [l[1],u[1]], [l[2],u[2]], ..., [l[n],u[n]] ].
• Choose a string Method from [ "InterP", "Simplex" ] depending on the method you want GLPK to use for solving the problem ("InterP" stands for the inter-point-method and "Simplex" for the simplex method)
• Choose a string MinMax from [ "Min", "Max" ] depending on whether you want $b$ to fulfill $c(b)=\min\{c(x)\mid x\in [l_{1},u_{1}]\times \cdots \times [l_{n},u_{n}]{\text{ is a solution to }}S\}$ or $c(b)=\max\{c(x)\mid x\in [l_{1},u_{1}]\times \cdots \times [l_{n},u_{n}]{\text{ is a solution to }}S\}$.

Then call

GLPK.LPSolve(c,EQ,LE,GE,B,Method,MinMax)

to get the desired solution as a list b = [b1,...,bn] or the empty list [] if the given system of (in)equalities is unsatisfiable.

Solving Mixed Integer Problems

See also: GLPK.MIPSolve

Let $I,J\subseteq \{1,\ldots ,n\}$ with $I\cap J=\emptyset$. If additionally, a solution $b=(b_{1},\ldots ,b_{n})$ with $b_{i}\in \mathbb {N}$ for $i\in I$ and $b_{j}\in \{0,1\}$ for $j\in J$ is searched, then one can use the function GLPK.MIPSolve. Together with c, EQ, LE, GE, B and MinMax from above, the code

GLPK.MIPSolve(c,EQ,LE,GE,B,Method,MinMax)

produces the desired solution or [] if the given system has no such solution.