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{\mathbb{N}}$ and $P=\mathbb{\mathbb{Q}}[x_1,\dots ,x_n]$. Let $f_1,\dots ,f_{s_1},g_1,\dots ,g_{s_2},h_1,\dots ,h_{s_3},c\in P$ be linear polynomials and let $l_1,\dots ,l_n,u_1,\dots ,u_n\in \mathbb{\mathbb{Q}}\cup \{-\mathrm{\infty },\mathrm{\infty }\}$. Let $S$ be the system of polynomial (in)equations

$\{\begin{array}{ccc}{f}_1(b)& =& 0\\ ⋮& ⋮& ⋮\\ f_{s_1}(b)& =& 0\\ g_1(b)& \le & 0\\ ⋮& ⋮& ⋮\\ g_{s_2}(b)& \le & 0\\ h_1(b)& \ge & 0\\ ⋮& ⋮& ⋮\\ h_{s_3}(b)& \ge & 0.\end{array}$

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,\dots ,f_{s_1}\}$, let LE be the list $\{g_1,\dots ,g_{s_2}\}$, and let GE be the list $\{h_1,\dots ,h_{s_3}\}$.
• Let l and u be lists with l[i]$=l_i$ if $l_i\in \mathbb{\mathbb{Q}}$ (resp. u[i]$=u_i$ if $u_i\in \mathbb{\mathbb{Q}}$) and l[i] = "" if $l_i=-\mathrm{\infty }$ (resp. u[i] = "" if $u_i=\mathrm{\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

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

to get the desired solution as a list b = [b1,...,bn].