Difference between revisions of "ApCoCoA-1:GLPK.L01PSolve"
From ApCoCoAWiki
m (replaced <quotes> tag by real quotes) |
|||
| (5 intermediate revisions by 3 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/> | <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. | 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. | ||
| Line 17: | Line 17: | ||
<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>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 ( | + | <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> | ||
| Line 32: | Line 33: | ||
QStrategy:=0; | QStrategy:=0; | ||
CStrategy:=0; | CStrategy:=0; | ||
| − | MinMax:= | + | MinMax:="Max"; |
-- Then we compute the solution with | -- Then we compute the solution with | ||
| Line 63: | Line 64: | ||
QStrategy:=1; | QStrategy:=1; | ||
CStrategy:=0; | CStrategy:=0; | ||
| − | MinMax:= | + | MinMax:="Max"; |
-- Then we compute the solution with | -- Then we compute the solution with | ||
| Line 90: | Line 91: | ||
QStrategy:=0; | QStrategy:=0; | ||
CStrategy:=1; | CStrategy:=1; | ||
| − | MinMax:= | + | MinMax:="Max"; |
-- Then we compute the solution with | -- Then we compute the solution with | ||
| Line 112: | Line 113: | ||
<type>apcocoaserver</type> | <type>apcocoaserver</type> | ||
<type>linear_programs</type> | <type>linear_programs</type> | ||
| + | <type>poly_system</type> | ||
</types> | </types> | ||
| − | <key> | + | <key>l01psolve</key> |
<key>solve linear programm</key> | <key>solve linear programm</key> | ||
<key>solve lp</key> | <key>solve lp</key> | ||
| − | <key>GLPK. | + | <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]
-------------------------------
