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

From ApCoCoAWiki
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.IPCSolve</title>
 
<title>GLPK.IPCSolve</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>
 
<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>
 
<syntax>
GLPK.IPCSolve(F:LIST, QStrategy:INT, CStrategy:INT, MinMax:STRING)
+
GLPK.IPCSolve(F:LIST, QStrategy:INT, CStrategy:INT, MinMax:STRING):LIST
 
</syntax>
 
</syntax>
 
<description>
 
<description>
Line 15: Line 16:
 
<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 (<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>
  
Line 29: Line 31:
 
QStrategy:=0;
 
QStrategy:=0;
 
CStrategy:=0;
 
CStrategy:=0;
MinMax:=<quotes>Max</quotes>;
+
MinMax:="Max";
  
 
-- Then we compute the solution with
 
-- Then we compute the solution with
Line 61: Line 63:
 
QStrategy:=1;
 
QStrategy:=1;
 
CStrategy:=0;
 
CStrategy:=0;
MinMax:=<quotes>Max</quotes>;
+
MinMax:="Max";
  
 
-- Then we compute the solution with
 
-- Then we compute the solution with
Line 89: Line 91:
 
QStrategy:=0;
 
QStrategy:=0;
 
CStrategy:=1;
 
CStrategy:=1;
MinMax:=<quotes>Max</quotes>;
+
MinMax:="Max";
  
 
-- Then we compute the solution with
 
-- Then we compute the solution with
Line 119: Line 121:
 
<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:31, 29 October 2020

This article is about a function from ApCoCoA-1.

GLPK.IPCSolve

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

Syntax

GLPK.IPCSolve(F:LIST, 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 uses Integer Polynomial Conversion (IPC) along with some strategies from propositional logic to model a mixed integer linear programming problem. Then the modelled mixed integer linear programming problem is solved using glpk.


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

  • @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
    ];

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

-- Then we compute the solution with

GLPK.IPCSolve(F, QStrategy, CStrategy, MinMax);

-- The result will be the following:
Modelling the system as a mixed integer programming problem. 
QStrategy: Standard, CStrategy: Standard.
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]
];


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

-- Then we compute the solution with

GLPK.IPCSolve(F, QStrategy, CStrategy, MinMax);

-- The result will be the following:

Modelling the system as a mixed integer programming problem. 
QStrategy: LinearPartner, CStrategy: Standard.
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]
     ];


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

-- Then we compute the solution with

GLPK.IPCSolve(F, QStrategy, CStrategy, MinMax);

-- The result will be the following:

Modelling the system as a mixed integer programming problem. 
QStrategy: Standard, CStrategy: CubicParnterDegree2.
Model is ready to solve with GLPK...

Solution Status: INTEGER OPTIMAL
Value of objective function: 1

[0, 0, 1]
-------------------------------