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: The GLPK-Program glpsol must be in the ApCoCoA package directory /binaries/glpk/examples and you must have the permissions to read and write in this directory.

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

Usage

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\}$ .