Petrozavodsk State University
Department of Computer Science

Log In

Nickname:
Password:
 

(you may also continue working as anonymous user, but your profile and limits information will not be saved)

Server Load

134 active users
0 registered users
0 solver tasks
0 generator tasks

ANLDE system description

The Web-SynDic system works with homogeneous ANLDE systems (ANLDE systems in short). The ANLDE system is a system of nonnegative linear Diophantine equations

I x = A x

where matrix A is a matrix with non-negative integers and matrix I is a (0,1)-integer matrix with the following property: each unknown has at most one non-zero coefficient in matrix I. See the User Manual (section "ANLDE system theory") for more formal definition.

Samples of ANLDE systems

Copy (with or without #-comment lines) any of these ANLDE systems into the clipboard, move to corresponding processing a single ANLDE system, or a set of ANLDE systems forms and paste back the ANLDE system(s) to the input form(s).

Simple ANLDE system 1

# A very simple case
x = y

Simple ANLDE system 2

This is the same as x = y, but in the standard ANLDE form.

x + y = 2*y

Simple ANLDE system 3

This system also is an ANLDE system; it has only zero-solution.

# It is satisfied by the only solution x=y=z=0
x + y + z = 0

Simple ANLDE system 4

Another example of a system with only zero-solution.

# It is satisfied by the only solution x=y=0
x = 2*y
y = x

Simple ANLDE system 5

This is slightly more complex description of x=y.
# (2x2)-ANLDE system with
# non-trivial solutions
x = y
y = x

Typical (2x4)-ANLDE system 1

This simple example is from Dmitry Korzun's PhD Thesis.

# It has 2 minimal solutions
x1 + x2 = 2*x1 + 3*x3
x3 + x4 = x1 + 2*x2 + x3

Typical (2x4)-ANLDE system 2

The same as previous one, but not in the standard ANLDE form.

x2 = x1 + 3*x3
x4 = x1 + 2*x2

ANLDE system with one equation

Only unit coefficient on the left-hand side; arbitrary positive integers on the right-hand side.

# It has 40 minimal solutions!
x1 + x2 + x3 = 5*y1 + 2*y2 + y3 + 3*y4

In the standard ANLDE form this equation is rewritten as:

x1 + x2 + x3 + y1 + y2 + y3 + y4 = 5*y1 + 2*y2 + y3 + 3*y4

Also some ANLDE systems or a set of ANLDE systems are hard for processing using alternative solvers, but not for the syntactic algorithm.

One ANLDE system

# many basis solutions
# hard for slopes
# easy for syntactic & lp_solve

x0 +x2 = x2 + c + 10*x1
y1 + y2 = 10*x2 + c
z1 + z2 = 2*c + y1
x1 = 2*c + z1
c = 2*x2 + 9*y1

# small basis
# hard for slopes
# easy for syntactic & lp_solve

x1 = 9*x3 + 12*x8 + 14*x9 + 4*x10
x3 + x10 = 5*x8 + 3*x9 + 7*x10
x8 + x4 = 9*x8 + 8*x9 + 13*x10
x5 = 13*x8 + 9*x9 + 10*x10 + 2*x6
x9 + x7 = 6*x8 + 10*x9 + 14*x10
x6 = x8 + x9 + x10

# simple basis
# hard for slopes
# easy for syntactic & lp_solve

x1 = 29*x1 + 40*x3 + 61*x4 + 56*x10 + 19*x11
x2 + x11 = 82*x1 + x2 + 27*x3 + 12*x4 + 13*x10 + 48*x11
x3 = 42*x1 + 13*x3 + 19*x4 + 58*x10 + 15*x11
x4 = 74*x1 + 35*x3 + 71*x4 + 27*x10 + 59*x11
x5 + x9 + x10 = 32*x1 + 39*x2 + 39*x4 + x5 + x9 + 51*x10 + 63*x11
x6 = 98*x1 + 3*x3 + 19*x4 + x6 + 91*x10 + 27*x11
x7 = 55*x1 + 20*x3 + 66*x4 + x7 + 17*x10 + 75*x11
x8 = 84*x1 + 98*x3 + 2*x4 + x8 + 96*x10 + 12*x11

# many basis solutions
# hard for slopes
# easy for syntactic & lp_solve

x1 + x9 + x10 = 6*x9 + 4*x10 + 4*x8 + 2*x11 + 3*x12 + 3*x13 + 2*x14
x8 + x2 = 2*x9 + 2*x10 + 4*x8 + x11 + 2*x12 + 2*x13 + 3*x14 + x3
x3 = 6*x9 + 4*x10 + 3*x8 + 4*x11 + 3*x12 + 5*x13 + x14
x13 + x14 + x4 = 3*x9 + 4*x10 + 5*x8 + 3*x11 + 7*x13 + 3*x14
x11 + x12 + x5 = 9*x9 + 6*x10 + x8 + 3*x11 + 6*x12 + x13 + 2*x14
x6 = 7*x9 + 5*x10 + x8 + 3*x11 + 7*x12 + 6*x13 + 9*x14
x7 = 6*x9 + 4*x10 + 5*x8 + 5*x11 + 9*x12 + 8*x13 + 5*x14

# easy for syntactic
# hard for lp_solve
# unsolvable for slopes

x1 = x8 + 17*x11 + 15*x12 + 8*x13 + 16*x14 + 37*x15
x2 = x8 + 43*x11 + 3*x12 + 49*x13 + 41*x14 + 43*x15
x3 = x8 + 27*x11 + 56*x12 + 49*x13 + 59*x14 + 11*x15
x14 + x4 = x8 + 5*x11 + 49*x12 + 55*x13 + 39*x14 + 34*x15
x12 + x5 = x8 + 28*x11 + 35*x12 + 4*x13 + 55*x14 + 21*x15
x15 + x6 = x8 + 22*x11 + 51*x12 + 34*x13 + 34*x14 + 23*x15
x7 = x8 + 45*x11 + 33*x12 + 49*x13 + 36*x14 + 27*x15
x8 = 48*x11 + 37*x12 + 12*x13 + 36*x14 + 35*x15
x9 = 90*x11 + 40*x12 + 40*x13 + 44*x14 + 36*x15
x11 + x13 + x10 = 96*x11 + 35*x12 + 75*x13 + 34*x14 + 35*x15
A set of ANLDE systems
# hard for slopes, but not for syntactic & lp_solve

x1 = 9*x3 + 12*x8 + 14*x9 + 4*x10
x3 = 5*x8 + 3*x9 + 6*x10
x8 + x4 = 9*x8 + 8*x9 + 13*x10
x5 = 13*x8 + 9*x9 + 10*x10 + 2*x6
x9 + x7 = 6*x8 + 10*x9 + 14*x10
x6 = x8 + x9
x10 = 2*x6

%

x1 = 9*x3 + 12*x8 + 14*x9 + 4*x10
x3 + x10 = 5*x8 + 3*x9 + 7*x10
x8 + x4 = 9*x8 + 8*x9 + 13*x10
x5 = 13*x8 + 9*x9 + 10*x10 + 2*x6
x9 + x7 = 6*x8 + 10*x9 + 14*x10
x6 = x8 + x9 + x10
    
%

x1 + x2 = 2*x1 + 3*x3
x3 + x4 = x1 + 2*x4 + x3

# hard for lp_solve & slopes, but not for syntactic

x1 = 9*x3 + 12*x8 + 14*x9 + 4*x10
x3 = 5*x8 + 3*x9 + 6*x10
x8 + x4 = 9*x8 + 8*x9 + 13*x10
x5 = 13*x8 + 9*x9 + 10*x10 + 2*x6
x9 + x7 = 6*x8 + 10*x9 + 14*x10
x6 = x8 + x9
x10 = 2*x6
    
%

x1 = 9*x3 + 12*x8 + 14*x9 + 4*x10
x3 + x10 = 5*x8 + 3*x9 + 7*x10
x8 + x4 = 9*x8 + 8*x9 + 13*x10
x5 = 13*x8 + 9*x9 + 10*x10 + 2*x6
x9 + x7 = 6*x8 + 10*x9 + 14*x10
x6 = x8 + x9 + x10

%

x1 = x8 + 17*x11 + 15*x12 + 8*x13 + 16*x14 + 37*x15
x2 = x8 + 43*x11 + 3*x12 + 49*x13 + 41*x14 + 43*x15
x3 = x8 + 27*x11 + 56*x12 + 49*x13 + 59*x14 + 11*x15
x14 + x4 = x8 + 5*x11 + 49*x12 + 55*x13 + 39*x14 + 34*x15
x12 + x5 = x8 + 28*x11 + 35*x12 + 4*x13 + 55*x14 + 21*x15
x15 + x6 = x8 + 22*x11 + 51*x12 + 34*x13 + 34*x14 + 23*x15
x7 = x8 + 45*x11 + 33*x12 + 49*x13 + 36*x14 + 27*x15
x8 = 48*x11 + 37*x12 + 12*x13 + 36*x14 + 35*x15
x9 = 90*x11 + 40*x12 + 40*x13 + 44*x14 + 36*x15
x11 + x13 + x10 = 96*x11 + 35*x12 + 75*x13 + 34*x14 + 35*x15

Version 1.0
Valid HTML 4.01! Valid CSS! Petrozavodsk State University, Department of Computer Science
Web-SynDic Team