Simplex Algorithm

[ftneek]

(12-03-2024 06:05 PM)nojatij Wrote:  Hi! Can you please write a guide on how to use your library?

Hi! I plan to write a complete documentation / tutorial sometime soon, but in the meantime I will try to give a brief introduction. The most important command is simplex(), because it gives access to most of the solver's features.

Code:

// simplex(a,[dir],[integers],[binary],[unrestricted]) accepts 1-5 arguments
// 'a' is a linear program as an augmented matrix, [A| b
//                                                  c|-z0], where
// A is the constraint matrix
// b is the right hand side of the constraints as a column
// c is the objective function row
// z0 is the constant coefficient of the objective function
// If there are any "=" constraints, they should be the first rows of the linear program.
// If there are any ">=" constraints, they should be the last rows of the linear program.
// The objective function should be the final row of the linear program, with the constant negated in the last index.
// [dir] is a list of 2 items; dir[1] is the number of "=" constraints and dir[2] is the number of ">=" constraints.
// a positive value for dir[1] indicates maximization, a negative value indicates minimization. for no "=" and max use inf, for min use -inf
// optionally, provide only dir[1] (not a list) for no ">="
// 'integers' is a list of integer variable indices.
// 'binary' is a list of binary variable indices.
// 'unrestricted' is a list of variable indices without nonnegative restriction.

When you use the 'integers' or the 'binary' argument it will use Gomory's Plane Cutting Algorithm to solve it, otherwise it just uses the Simplex algorithm.

'dir' currently has a few ways to use it. To be consistent you can always input it as a list of 2 items. The first item is the number of '=' constraints and should be positive for maximization or negative for minimization. For no '=' you can you +inf or -inf. The second item in the list is the number of '>=' constraints. When there are no '>=' constraints, you can put it as a single number without the list delimiters.

For example, to solve the system:
minimize 2x+5y
subject to
3x-y=1
x-y≤5
where x,y are nonnegative and integer

We can type

Code:

a:=[[3,-1,1],[1,-1,5],[2,5,0]];
dir:=-1;    // (or we can use dir:=[-1,0])
integers:=[1,2];
simplex(a,dir,integers)

Here, dir:=[-1,0] means this is a minimization problem, there is 1 '=' constraint, and are 0 '>=' constraints.

Here, both variables have integer restriction, so integers:=[1,2].

For this problem we get:
\[[12,\left[\begin{array}{cccccc}
1 & 0 & 0 & -1 & 1 & 1 \\
0 & 0 & 1 & -2 & 1 & 6 \\
0 & 1 & 0 & -3 & 2 & 2 \\
0 & 0 & 0 & 17 & -12 & -12
\end{array}\right] ,[1,3,2],2,\left[\begin{array}{c}
1 \\
2 \\
6 \\
0 \\
0
\end{array}\right] ]\]

simplex() returns a list of 5 items, most important are the first and the last item:
The first item is the minimum of 12.
The last item is the solution vector as a column, here x=1 and y=2. The extra solutions in the vector (6,0,0) correspond to slack variables, Gomory cut variables, and artificial variables.

The other items, if you're interested:
The second item from the list is the linear program matrix after the final iteration.
The third item is the list of current (final) basic variables indices.
The 4th item is the number of times the 'pivot1' command was used (to get an idea of performance against other solvers).

Another example:
// 2z1 + 3z2 + 4z3 ≤ 6
// 4z1 + 2z2 + 5z3 ≤ 5
// max 22z1 +20z2 +40z3 = c
// z1,z2,z3 ≥ 0

simplex([[2,3,4,6],[4,2,5,5],[22,20,40,0]],lpmax) ->
\[[\frac{320}{7},\left[\begin{array}{cccccc}
\frac{-6}{7} & 1 & 0 & \frac{5}{7} & \frac{-4}{7} & \frac{10}{7} \\
\frac{8}{7} & 0 & 1 & \frac{-2}{7} & \frac{3}{7} & \frac{3}{7} \\
\frac{46}{7} & 0 & 0 & \frac{20}{7} & \frac{40}{7} & \frac{320}{7}
\end{array}\right] ,[2,3],2,\left[\begin{array}{c}
0 \\
\frac{10}{7} \\
\frac{3}{7} \\
0 \\
0
\end{array}\right] ]\]

There is also the test file included with the source code which contains more examples of lp problems and the corresponding input to the simplex command.

(12-03-2024 06:05 PM)nojatij Wrote:  And is there a way in your library to output each iteration of the simplex method?

Not exactly, but for now you can try debug(simplex(...)) to run the program in debug mode and execute it step by step and see the variables. I might be able to add a a verbose mode / step by step mode to print some things to the terminal. Is there anything in particular you'd like to see on each iteration?

Let me know if you need more clarification or if you have any other questions and I'll try to help.

[ftneek]

Dec 6, 2024:
- Full Xcas compatibility for all commands. Load the simplex.xws file in Xcas to try the examples. All tests passed in Xcas, but I think one failed in an Xcas web session.
- BasisID commands moved to the simplex file.
- adds pdf documentation for available commands.

[nojatij]

(12-06-2024 09:15 AM)ftneek Wrote:  Dec 6, 2024:
- Full Xcas compatibility for all commands. Load the simplex.xws file in Xcas to try the examples. All tests passed in Xcas, but I think one failed in an Xcas web session.
- BasisID commands moved to the simplex file.
- adds pdf documentation for available commands.

Thanks a lot for the documentation! Actually bought a calculator almost because of your library, haha