# Package glpk

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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 ${\displaystyle n\in \mathbb {N} }$ and ${\displaystyle P=\mathbb {Q} [x_{1},\ldots ,x_{n}]}$. Let ${\displaystyle 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 ${\displaystyle l_{1},\ldots ,l_{n},u_{1},\ldots ,u_{n}\in \mathbb {Q} \cup \{-\infty ,\infty \}}$. Let ${\displaystyle S}$ be the system of polynomial (in)equations

${\displaystyle \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 ${\displaystyle b\in [l_{1},u_{1}]\times \cdots \times [l_{n},u_{n}]}$ to ${\displaystyle S}$ such that ${\displaystyle 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 ${\displaystyle \{f_{1},\ldots ,f_{s_{1}}\}}$, let LE be the list ${\displaystyle \{g_{1},\ldots ,g_{s_{2}}\}}$, and let GE be the list ${\displaystyle \{h_{1},\ldots ,h_{s_{3}}\}}$.
• Let l and u be lists with l[i]${\displaystyle =l_{i}}$ if ${\displaystyle l_{i}\in \mathbb {Q} }$ (resp. u[i]${\displaystyle =u_{i}}$ if ${\displaystyle u_{i}\in \mathbb {Q} }$) and l[i] = "" if ${\displaystyle l_{i}=-\infty }$ (resp. u[i] = "" if ${\displaystyle 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 ${\displaystyle b}$ to fulfill ${\displaystyle 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 ${\displaystyle 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].