Difference between revisions of "Package glpk"

From ApCoCoAWiki
(added MIPSolve, categories, version and windows info)
m (upsi!)
 
(One intermediate revision by the same user not shown)
Line 4: Line 4:
 
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.
 
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.
  
<em>Important</em>: For usage under linux, the GLPK-Program glpsol must be in the ApCoCoA package directory under <code>packages/binaries/glpk/examples/glpsol</code> and you must have the permissions to read and write in this directory. For Windows, the glsol.exe has to be in the folder <code>\packages\binaries\glpk\w64\glpsol.exe</code>. If you installed ApCoCoA-2 together with the GUI, this should already be the case.
+
<em>Important</em>: For usage under linux, the GLPK-Program glpsol must be in the ApCoCoA package directory under <code>packages/binaries/glpk/examples/glpsol</code> and you must have the permissions to read and write in this directory. For Windows, the glsol.exe has to be in the folder <code>packages\binaries\glpk\w64\glpsol.exe</code>. If you installed ApCoCoA-2 together with the GUI, this should already be the case.
  
 
The source code of GLPK can be downloaded at [http://www.gnu.org/software/glpk/].
 
The source code of GLPK can be downloaded at [http://www.gnu.org/software/glpk/].
Line 22: Line 22:
 
   h_{s_3}(b) & \geq & 0.
 
   h_{s_3}(b) & \geq & 0.
 
\end{array}\right.</math>
 
\end{array}\right.</math>
Then the function <code>[[/GLPK.LPSolve/]]</code> can be used to find solution <math>b \in [l_1,u_1] \times \cdots \times [l_n,u_n]</math> to <math>S</math> such that <math>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\}</math> in the following way.
+
Then the function <code>[[/GLPK.LPSolve/]]</code> can be used to find solution <math>b = (b_1,\ldots,b_n) \in [l_1,u_1] \times \cdots \times [l_n,u_n]</math> to <math>S</math> such that <math>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\}</math> in the following way.
  
 
*Let <code>EQ</code> be the list <math>\{f_1,\ldots,f_{s_1}\}</math>, let <code>LE</code> be the list <math>\{g_1,\ldots,g_{s_2}\}</math>, and let <code>GE</code> be the list <math>\{h_1,\ldots,h_{s_3}\}</math>.
 
*Let <code>EQ</code> be the list <math>\{f_1,\ldots,f_{s_1}\}</math>, let <code>LE</code> be the list <math>\{g_1,\ldots,g_{s_2}\}</math>, and let <code>GE</code> be the list <math>\{h_1,\ldots,h_{s_3}\}</math>.
*Let <code>l</code> and <code>u</code> be lists with <code>l[i]</code><math> = l_i</math> if <math>l_i \in \mathbb{Q}</math> (resp. <code>u[i]</code><math> = u_i</math> if <math>u_i \in \mathbb{Q}</math>) and <code>l[i] = ""</code>  if <math>l_i = - \infty</math> (resp. <code>u[i] = ""</code> if <math>u_i = \infty</math>). Furthermore, we set <code>B := [ [l[1],u[1]], [l[2],u[2]], ..., [l[n],u[n]] ]</code>.
+
*Let <code>l</code> and <code>u</code> be the lists containing the upper and lower bounds for the <math>b_i</math> with <code>l[i]</code><math> = l_i</math> and <code>u[i]</code><math> = u_i</math>, if both are rational numbers. Instead of <math>\infty</math> and <math>- \infty</math>, write <code>l[i] = ""</code> or <code>u[i] = ""</code>. Set <code>B := [ [l[1],u[1]], [l[2],u[2]], ..., [l[n],u[n]] ]</code>.
 
*Choose a string <code>Method</code> from <code>[ "InterP", "Simplex" ]</code> depending on the method you want GLPK to use for solving the problem (<code>"InterP"</code> stands for the inter-point-method and <code>"Simplex"</code> for the simplex method)  
 
*Choose a string <code>Method</code> from <code>[ "InterP", "Simplex" ]</code> depending on the method you want GLPK to use for solving the problem (<code>"InterP"</code> stands for the inter-point-method and <code>"Simplex"</code> for the simplex method)  
 
*Choose a string <code>MinMax</code> from <code>[ "Min", "Max" ]</code> depending on whether you want <math>b</math> to fulfill <math>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\}</math> or <math>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\}</math>.
 
*Choose a string <code>MinMax</code> from <code>[ "Min", "Max" ]</code> depending on whether you want <math>b</math> to fulfill <math>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\}</math> or <math>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\}</math>.
Line 34: Line 34:
 
== Solving Mixed Integer Problems ==
 
== Solving Mixed Integer Problems ==
 
:''See also: [[/GLPK.MIPSolve/]]
 
:''See also: [[/GLPK.MIPSolve/]]
Let <math>I, J \subseteq \{1,\ldots,n\}</math> with <math>I \cap J = \emptyset</math>. If additionally, a solution <math>b = (b_1,\ldots,b_n)</math> with <math>b_i \in \mathbb{N}</math> for <math>i \in I</math> and <math>b_j \in \{0,1\}</math> for <math>j \in J</math> is searched, then one can use the function <code>[[/GLPK.MIPSolve/]]</code>. Together with <code>c</code>, <code>EQ</code>, <code>LE</code>, <code>GE</code>, <code>B</code> and <code>MinMax</code> from above, the code
+
Let <math>I, J \subseteq \{1,\ldots,n\}</math> be disjoint sets. If additionally, a solution <math>b = (b_1,\ldots,b_n)</math> with <math>b_i \in \mathbb{N}</math> for <math>i \in I</math> and <math>b_j \in \{0,1\}</math> for <math>j \in J</math> is searched, then one can use the function <code>[[/GLPK.MIPSolve/]]</code>. Together with <code>c</code>, <code>EQ</code>, <code>LE</code>, <code>GE</code>, <code>B</code> and <code>MinMax</code> from above, the code
<pre>GLPK.MIPSolve(c,EQ,LE,GE,B,Method,MinMax)</pre>
+
<pre>GLPK.MIPSolve(c,EQ,LE,GE,B,I,J,MinMax)</pre>
 
produces the desired solution or <code>[]</code> if the given system has no such solution.
 
produces the desired solution or <code>[]</code> if the given system has no such solution.
  
 
[[Category:ApCoCoA Packages]]
 
[[Category:ApCoCoA Packages]]
 
[[Category:Package glpk]]
 
[[Category:Package glpk]]

Latest revision as of 15:48, 1 November 2020

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 and . Let be linear polynomials and let . Let be the system of polynomial (in)equations

Then the function GLPK.LPSolve can be used to find solution to such that in the following way.

  • Let EQ be the list , let LE be the list , and let GE be the list .
  • Let l and u be the lists containing the upper and lower bounds for the with l[i] and u[i], if both are rational numbers. Instead of and , 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 to fulfill or .

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 be disjoint sets. If additionally, a solution with for and for 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,I,J,MinMax)

produces the desired solution or [] if the given system has no such solution.