Difference between revisions of "ApCoCoA-1:GLPK.L01PSolve"

From ApCoCoAWiki
m (replaced <quotes> tag by real quotes)
 
(8 intermediate revisions by 4 users not shown)
Line 1: Line 1:
 +
{{Version|1}}
 
<command>
 
<command>
 
<title>GLPK.L01PSolve</title>
 
<title>GLPK.L01PSolve</title>
 
<short_description>Solve a system of polynomial equations over <tt>F_2</tt> for one solution in <tt>F_2^n</tt>.</short_description>
 
<short_description>Solve a system of polynomial equations over <tt>F_2</tt> for one solution in <tt>F_2^n</tt>.</short_description>
 
<syntax>
 
<syntax>
−
GLPK.L01PSolve(F:LIST, CuttingNumber:INT, QStrategy:INT, CStrategy:INT, MinMax:STRING)
+
GLPK.L01PSolve(F:LIST, CuttingNumber:INT, QStrategy:INT, CStrategy:INT, MinMax:STRING):LIST
 
</syntax>
 
</syntax>
 
<description>
 
<description>
 
<em>Please note:</em> The function(s) explained on this page is/are using the <em>ApCoCoAServer</em>. You will have to start the ApCoCoAServer in order to use it/them.
 
<em>Please note:</em> The function(s) explained on this page is/are using the <em>ApCoCoAServer</em>. You will have to start the ApCoCoAServer in order to use it/them.
 +
<par/>
 +
This function finds one solution in <tt>F_2^n</tt> of a system of polynomial equations over the field <tt>F_2</tt>. It operates in two stages. Firstly, it models the problem of finding one solution of given polynomial system into a mixed integer linear programming problem. For this the system is first converted into an equivalent CNF form and then the CNF form is converted into a system of equalities and inequalities. Secondly, the mixed integer linear programming model is solved using glpk.
 +
  
 
<itemize>
 
<itemize>
 
<item>@param <em>F</em>: A List containing the polynomials of the given system.</item>  
 
<item>@param <em>F</em>: A List containing the polynomials of the given system.</item>  
 
<item>@param <em>CuttingNumber</em>: Maximal support-length of the linear polynomials for conversion to CNF. The possible value could be from 3 to 6. </item>
 
<item>@param <em>CuttingNumber</em>: Maximal support-length of the linear polynomials for conversion to CNF. The possible value could be from 3 to 6. </item>
−
<item>@param <em>QStrategy</em>: Strategy for quadratic substitution. 0 - Standard; 1 - Linear Partner; and 2 - Double Linear Partner;</item>
+
<item>@param <em>QStrategy</em>: Strategy for quadratic substitution. 0 - Standard; 1 - Linear Partner; 2 - Double Linear Partner; 3 - Quadratic Partner;</item>
 
<item>@param <em>CStrategy</em>: Strategy for cubic substitution. 0 - Standard; and 1 - Quadratic Partner;</item>
 
<item>@param <em>CStrategy</em>: Strategy for cubic substitution. 0 - Standard; and 1 - Quadratic Partner;</item>
−
<item>@param <em>MinMax</em>: Optimization direction i.e. minimization (<quotes>Min</quotes>) or maximization (<quotes>Max</quotes>).</item>
+
<item>@param <em>MinMax</em>: Optimization direction i.e. minimization ("Min") or maximization ("Max").</item>
 +
<item>@return A list containing a zero of the system F.</item>
 
</itemize>
 
</itemize>
  
 
<example>
 
<example>
−
-- We want to maximize the Function y = - 1/2x,  
+
Use Z/(2)[x[1..4]];
−
-- with the two conditions y ≤ 6 - 3/4x and y ≥ 1 - x and the bounds 0 ≤ x ≤ 6 and 1/3 ≤ y ≤ 4.
+
F:=[
 +
    x[1]x[2] + x[2]x[3] + x[2]x[4] + x[3]x[4] + x[1] + x[3] + 1,
 +
    x[1]x[2] + x[1]x[3] + x[1]x[4] + x[3]x[4] + x[2] + x[3] + 1,
 +
    x[1]x[2] + x[1]x[3] + x[2]x[3] + x[3]x[4] + x[1] + x[4] + 1,
 +
    x[1]x[3] + x[2]x[3] + x[1]x[4] + x[2]x[4] + 1
 +
    ];
 +
 
 +
CuttingNumber:=6;
 +
QStrategy:=0;
 +
CStrategy:=0;
 +
MinMax:="Max";
 +
 
 +
-- Then we compute the solution with
 +
 
 +
GLPK.L01PSolve(F, CuttingNumber, QStrategy, CStrategy, MinMax);
 +
 
 +
-- The result will be the following:
 +
 
 +
Converting to CNF with CuttingLength: 6, QStrategy: Standard, CStrategy: Standard.
 +
Converting CNF to system of equalities and inequalities...
 +
Model is ready to solve with GLPK...
 +
Solution Status: INTEGER OPTIMAL
 +
Value of objective function: 2
 +
[0, 1, 0, 1]
 +
-------------------------------
 +
</example>
 +
 
 +
 
 +
<example>
 +
Use S::=Z/(2)[x[1..5]];
 +
F:=[
 +
x[1]x[5] + x[3]x[5] + x[4]x[5] + x[1] + x[4],
 +
x[1]x[2] + x[1]x[4] + x[3]x[4] + x[1]x[5] + x[2]x[5] + x[3]x[5] + x[1] + x[4] + x[5] + 1,
 +
x[1]x[2] + x[4]x[5] + x[1] + x[2] + x[4],
 +
x[1]x[4] + x[3]x[4] + x[2]x[5] + x[1] + x[2] + x[4] + x[5] + 1,
 +
x[1]x[4] + x[2]x[4] + x[3]x[4] + x[2]x[5] + x[4]x[5] + x[1] + x[2] + x[4] + x[5]
 +
];
 +
 
 +
CuttingNumber:=6;
 +
QStrategy:=1;
 +
CStrategy:=0;
 +
MinMax:="Max";
 +
 
 +
-- Then we compute the solution with
 +
 
 +
GLPK.L01PSolve(F, CuttingNumber, QStrategy, CStrategy, MinMax);
 +
 
 +
-- The result will be the following:
 +
 
 +
Converting to CNF with CuttingLength: 6, QStrategy: LinearPartner, CStrategy: Standard.
 +
Converting CNF to system of equalities and inequalities...
 +
Model is ready to solve with GLPK...
 +
Solution Status: INTEGER OPTIMAL
 +
Value of objective function: 4
 +
[1, 1, 1, 1, 0]
 +
-------------------------------
 +
</example>
 +
 
 +
<example>
 +
Use ZZ/(2)[x[1..3]];
 +
F := [ x[1]x[2]x[3] + x[1]x[2] + x[2]x[3] + x[1] + x[3] +1,
 +
      x[1]x[2]x[3] + x[1]x[2] + x[2]x[3] + x[1] + x[2],
 +
      x[1]x[2] + x[2]x[3] + x[2]
 +
    ];
  
−
-- We prename the input of GLPK.MIPSolve-function.
+
CuttingNumber:=5;
−
Use S::=QQ[x,y];
+
QStrategy:=0;
−
OF := 1/2x + y;
+
CStrategy:=1;
−
LE := [3/4x + y - 6];
+
MinMax:="Max";
−
GE := [x + y - 1];
 
−
Bounds:=[[0,6], [1/3,4]];
 
−
IntNum:=[x,y];
 
  
 
-- Then we compute the solution with
 
-- Then we compute the solution with
−
GLPK.MIPSolve(OF, [], LE, GE, Bounds, IntNum, [], <quotes>Max</quotes>);
 
  
 +
GLPK.L01PSolve(F, CuttingNumber, QStrategy, CStrategy, MinMax);
  
−
-- And we achieve:
+
-- The result will be the following:
 +
 
 +
Converting to CNF with CuttingLength: 5, QStrategy: Standard, CStrategy: CubicParnterDegree2.
 +
Converting CNF to system of equalities and inequalities...
 +
Model is ready to solve with GLPK...
 
Solution Status: INTEGER OPTIMAL
 
Solution Status: INTEGER OPTIMAL
−
Value of objective function: 5
+
Value of objective function: 1
−
[x - 2, y - 4]
+
[0, 0, 1]
 +
-------------------------------
 
</example>
 
</example>
 +
  
 
</description>
 
</description>
Line 42: Line 113:
 
   <type>apcocoaserver</type>
 
   <type>apcocoaserver</type>
 
  <type>linear_programs</type>
 
  <type>linear_programs</type>
 +
<type>poly_system</type>
 
</types>
 
</types>
−
<key>mipsolve</key>
+
<key>l01psolve</key>
 
<key>solve linear programm</key>
 
<key>solve linear programm</key>
 
<key>solve lp</key>
 
<key>solve lp</key>
−
<key>GLPK.MIPSolve</key>
+
<key>GLPK.l01pSolve</key>
−
<wiki-category>Package_glpk</wiki-category>
+
<wiki-category>ApCoCoA-1:Package_glpk</wiki-category>
 
</command>
 
</command>

Latest revision as of 13:31, 29 October 2020

This article is about a function from ApCoCoA-1.

GLPK.L01PSolve

Solve a system of polynomial equations over F_2 for one solution in F_2^n.

Syntax

GLPK.L01PSolve(F:LIST, CuttingNumber:INT, QStrategy:INT, CStrategy:INT, MinMax:STRING):LIST

Description

Please note: The function(s) explained on this page is/are using the ApCoCoAServer. You will have to start the ApCoCoAServer in order to use it/them.

This function finds one solution in F_2^n of a system of polynomial equations over the field F_2. It operates in two stages. Firstly, it models the problem of finding one solution of given polynomial system into a mixed integer linear programming problem. For this the system is first converted into an equivalent CNF form and then the CNF form is converted into a system of equalities and inequalities. Secondly, the mixed integer linear programming model is solved using glpk.


  • @param F: A List containing the polynomials of the given system.

  • @param CuttingNumber: Maximal support-length of the linear polynomials for conversion to CNF. The possible value could be from 3 to 6.

  • @param QStrategy: Strategy for quadratic substitution. 0 - Standard; 1 - Linear Partner; 2 - Double Linear Partner; 3 - Quadratic Partner;

  • @param CStrategy: Strategy for cubic substitution. 0 - Standard; and 1 - Quadratic Partner;

  • @param MinMax: Optimization direction i.e. minimization ("Min") or maximization ("Max").

  • @return A list containing a zero of the system F.

Example

Use Z/(2)[x[1..4]];
F:=[
    x[1]x[2] + x[2]x[3] + x[2]x[4] + x[3]x[4] + x[1] + x[3] + 1, 
    x[1]x[2] + x[1]x[3] + x[1]x[4] + x[3]x[4] + x[2] + x[3] + 1, 
    x[1]x[2] + x[1]x[3] + x[2]x[3] + x[3]x[4] + x[1] + x[4] + 1, 
    x[1]x[3] + x[2]x[3] + x[1]x[4] + x[2]x[4] + 1
    ];

CuttingNumber:=6;
QStrategy:=0;
CStrategy:=0;
MinMax:="Max";

-- Then we compute the solution with

GLPK.L01PSolve(F, CuttingNumber, QStrategy, CStrategy, MinMax);

-- The result will be the following:

Converting to CNF with CuttingLength: 6, QStrategy: Standard, CStrategy: Standard.
Converting CNF to system of equalities and inequalities...
Model is ready to solve with GLPK...
Solution Status: INTEGER OPTIMAL
Value of objective function: 2
[0, 1, 0, 1]
-------------------------------


Example

Use S::=Z/(2)[x[1..5]];
F:=[
 x[1]x[5] + x[3]x[5] + x[4]x[5] + x[1] + x[4],
 x[1]x[2] + x[1]x[4] + x[3]x[4] + x[1]x[5] + x[2]x[5] + x[3]x[5] + x[1] + x[4] + x[5] + 1,
 x[1]x[2] + x[4]x[5] + x[1] + x[2] + x[4],
 x[1]x[4] + x[3]x[4] + x[2]x[5] + x[1] + x[2] + x[4] + x[5] + 1,
 x[1]x[4] + x[2]x[4] + x[3]x[4] + x[2]x[5] + x[4]x[5] + x[1] + x[2] + x[4] + x[5]
];

CuttingNumber:=6;
QStrategy:=1;
CStrategy:=0;
MinMax:="Max";

-- Then we compute the solution with

GLPK.L01PSolve(F, CuttingNumber, QStrategy, CStrategy, MinMax);

-- The result will be the following:

Converting to CNF with CuttingLength: 6, QStrategy: LinearPartner, CStrategy: Standard.
Converting CNF to system of equalities and inequalities...
Model is ready to solve with GLPK...
Solution Status: INTEGER OPTIMAL
Value of objective function: 4
[1, 1, 1, 1, 0]
-------------------------------

Example

Use ZZ/(2)[x[1..3]];
F := [ x[1]x[2]x[3] + x[1]x[2] + x[2]x[3] + x[1] + x[3] +1,
       x[1]x[2]x[3] + x[1]x[2] + x[2]x[3] + x[1] + x[2],
       x[1]x[2] + x[2]x[3] + x[2]
     ];

CuttingNumber:=5;
QStrategy:=0;
CStrategy:=1;
MinMax:="Max";

-- Then we compute the solution with

GLPK.L01PSolve(F, CuttingNumber, QStrategy, CStrategy, MinMax);

-- The result will be the following:

Converting to CNF with CuttingLength: 5, QStrategy: Standard, CStrategy: CubicParnterDegree2.
Converting CNF to system of equalities and inequalities...
Model is ready to solve with GLPK...
Solution Status: INTEGER OPTIMAL
Value of objective function: 1
[0, 0, 1]
-------------------------------





Retrieved from "http://apcocoa.uni-passau.de/wiki/index.php?title=ApCoCoA-1:GLPK.L01PSolve&oldid=16076"