# 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.

## Optimizing Linear Systems Of Equations

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=(b_{1},\ldots ,b_{n})\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 the lists containing the upper and lower bounds for the ${\displaystyle b_{i}}$ with l[i]${\displaystyle =l_{i}}$ and u[i]${\displaystyle =u_{i}}$, if both are rational numbers. Instead of ${\displaystyle \infty }$ and ${\displaystyle -\infty }$, write l[i] = "" or u[i] = "". 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

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

Let ${\displaystyle I,J\subseteq \{1,\ldots ,n\}}$ with ${\displaystyle I\cap J=\emptyset }$. If additionally, a solution ${\displaystyle b=(b_{1},\ldots ,b_{n})}$ with ${\displaystyle b_{i}\in \mathbb {N} }$ for ${\displaystyle i\in I}$ and ${\displaystyle b_{j}\in \{0,1\}}$ for ${\displaystyle 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.