Difference between revisions of "ApCoCoA-1:GLPK.RRPCSolve"
From ApCoCoAWiki
(New page: <command> <title>GLPK.RRPCSolve</title> <short_description>Solves a system of polynomial equations over <tt>F_2</tt> for one solution in <tt>F_2^n</tt>.</short_description> <syntax> GLPK.R...) |
m (replaced <quotes> tag by real quotes) |
||
| (3 intermediate revisions by 2 users not shown) | |||
| Line 1: | Line 1: | ||
| + | {{Version|1}} | ||
<command> | <command> | ||
<title>GLPK.RRPCSolve</title> | <title>GLPK.RRPCSolve</title> | ||
| Line 8: | Line 9: | ||
<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 (if exists) in <tt>F_2^n</tt> of a system of polynomial equations over the field <tt>F_2</tt>. This function uses Real Polynomial Conversion ( | + | This function finds one solution (if exists) in <tt>F_2^n</tt> of a system of polynomial equations over the field <tt>F_2</tt>. This function uses Real Polynomial Conversion (RPC) along with some standard rules, for linearizein 0-1 nonlinear polynomial functions into 0-1 linear polynomials, to model the solution of system F as a mixed integer linear programming problem. The linearization involves adding two kind of 0-1 linear constraints. Rule1 and Rule2 handle the first and the second kind of constriants respectively. Afterwards, the mixed integer linear programming problem is solved using glpk. Finally, an inverse conversion is applied to obtain the solution of the system F. |
| Line 15: | Line 16: | ||
<item>@param <em>Rule1</em>: Strategy for the first kind of constraints. 0 - standard; and 1 - non-standard;</item> | <item>@param <em>Rule1</em>: Strategy for the first kind of constraints. 0 - standard; and 1 - non-standard;</item> | ||
<item>@param <em>Rule2</em>: Strategy for the second kind of constraints. 0 - standard; and 0 to 3 - non-standard;</item> | <item>@param <em>Rule2</em>: Strategy for the second kind of constraints. 0 - standard; and 0 to 3 - non-standard;</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 polynomial system F.</item> | <item>@return A list containing a zero of the polynomial system F.</item> | ||
</itemize> | </itemize> | ||
| Line 30: | Line 31: | ||
Rule1:=0; | Rule1:=0; | ||
Rule2:=0; | Rule2:=0; | ||
| − | MinMax:= | + | MinMax:="Max"; |
-- Then we compute the solution with | -- Then we compute the solution with | ||
| Line 63: | Line 64: | ||
Rule1:=1; | Rule1:=1; | ||
Rule2:=0; | Rule2:=0; | ||
| − | MinMax:= | + | MinMax:="Max"; |
-- Then we compute the solution with | -- Then we compute the solution with | ||
| Line 90: | Line 91: | ||
Rule1:=0; | Rule1:=0; | ||
| − | Rule2:= | + | Rule2:=2; |
| − | MinMax:= | + | MinMax:="Max"; |
-- Then we compute the solution with | -- Then we compute the solution with | ||
| Line 100: | Line 101: | ||
Input ok... | Input ok... | ||
Modelling the system as a mixed integer programming problem. | Modelling the system as a mixed integer programming problem. | ||
| − | Rule1: 0, Rule2: | + | Rule1: 0, Rule2: 2. |
Model is ready to solve with GLPK... | Model is ready to solve with GLPK... | ||
| Line 121: | Line 122: | ||
<key>solve lp</key> | <key>solve lp</key> | ||
<key>GLPK.ipcsolve</key> | <key>GLPK.ipcsolve</key> | ||
| − | <wiki-category>Package_glpk</wiki-category> | + | <wiki-category>ApCoCoA-1:Package_glpk</wiki-category> |
</command> | </command> | ||
Latest revision as of 13:32, 29 October 2020
| This article is about a function from ApCoCoA-1. |
GLPK.RRPCSolve
Solves a system of polynomial equations over F_2 for one solution in F_2^n.
Syntax
GLPK.RRPCSolve(F:LIST, Rule1:INT, Rule2: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 (if exists) in F_2^n of a system of polynomial equations over the field F_2. This function uses Real Polynomial Conversion (RPC) along with some standard rules, for linearizein 0-1 nonlinear polynomial functions into 0-1 linear polynomials, to model the solution of system F as a mixed integer linear programming problem. The linearization involves adding two kind of 0-1 linear constraints. Rule1 and Rule2 handle the first and the second kind of constriants respectively. Afterwards, the mixed integer linear programming problem is solved using glpk. Finally, an inverse conversion is applied to obtain the solution of the system F.
@param F: A List containing the polynomials of the given system.
@param Rule1: Strategy for the first kind of constraints. 0 - standard; and 1 - non-standard;
@param Rule2: Strategy for the second kind of constraints. 0 - standard; and 0 to 3 - non-standard;
@param MinMax: Optimization direction i.e. minimization ("Min") or maximization ("Max").
@return A list containing a zero of the polynomial 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
];
Rule1:=0;
Rule2:=0;
MinMax:="Max";
-- Then we compute the solution with
GLPK.RRPCSolve(F, Rule1, Rule2, MinMax);
-- The result will be the following:
Input ok...
Modelling the system as a mixed integer programming problem.
Rule1: 0, Rule2: 0.
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] ]; Rule1:=1; Rule2:=0; MinMax:="Max"; -- Then we compute the solution with GLPK.RRPCSolve(F, Rule1, Rule2, MinMax); -- The result will be the following: Input ok... Modelling the system as a mixed integer programming problem. Rule1: 1, Rule2: 0. 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]
];
Rule1:=0;
Rule2:=2;
MinMax:="Max";
-- Then we compute the solution with
GLPK.RRPCSolve(F, Rule1, Rule2, MinMax);
-- The result will be the following:
Input ok...
Modelling the system as a mixed integer programming problem.
Rule1: 0, Rule2: 2.
Model is ready to solve with GLPK...
Solution Status: INTEGER OPTIMAL
Value of objective function: 1
[0, 0, 1]
-------------------------------
