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{\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

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,\dots ,n\}$ with $I\cap J=\mathrm{\varnothing }$. If additionally, a solution $b=(b_1,\dots ,b_n)$ with $b_i\in \mathbb{\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.