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

Line 7: | Line 7: | ||

<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 113: | Line 112: | ||

<type>linear_programs</type> | <type>linear_programs</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>Package_glpk</wiki-category> | ||

</command> | </command> |

## Revision as of 14:00, 14 December 2010

## 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)

### 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").

#### 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:=<quotes>Max</quotes>; -- 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:=<quotes>Max</quotes>; -- 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:=<quotes>Max</quotes>; -- 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] -------------------------------