Simplex Algorithm

[ftneek]

(11-20-2023 03:34 PM)Albert Chan Wrote:  Question about simplex_int(a,bv,v,art,ign,integers)

Code:

// Step 3: solve with new constraint
  a:=simplex_core(a,bv,v+1,0,ign);

From documentation, v is the number of variables (true + slack + artificial)
Since we keep addding slack variables to a, should (v+1) be more?

However, v is only used for simplex_core sol(a,v), so I guess doc is wrong.
It may meant to solve v leftmost variables.

And, why the +1?

What about simplex_int last argument, what is integers? How to setup problem with it?

---

I thought variable v is redundant = matrix columns - 1
Now that I know better, I am replacing art_row(v,art) as artrow(col,art)
If v=col-1, both matched. If not, using columns is safer.
Below will be on my next update.

>artrow(col,art):=append(makelist(k->k>col-art,2,col),0);
>artrow(9,2)      → [0,0,0,0,0,0,1,1,0]

Yes my mistake. Technically 'v' should increase every iteration, not just once. But the user may not care about these extra variable solutions, so for now it's probably not a big deal, but can be fixed. I think I meant to do something like ++v. But I think how the 'v' argument is handled may change in the future, probably when I figure out how to implement "unrestricted" variables (and/or symbolic input). simplex_core works with unrestricted variables, but again for now you have to put it in standard form yourself.

Ex: x1 is unrestricted (<=0 or >=0) and integer
-> x1=x1'-x1'' where x1',x1''>=0 and integer

From user's perspective, the original system only has v variables. But once in standard form we've added columns for slack and artificial variables (and fixed unrestricted variables), so from simplex_core perspective we should have v=col-1. As you say, the only difference v has right now is the number of left most solutions to read. If we had unrestricted variables, the solution user expects != solve original v leftmost variables, we have to recover what the unrestricted variables are from the xi=xi'-xi'' relation.

I gave an example a few comments ago, integers is a list of variables with integer restriction. For example
x1,x2 integer -> integers:=[1,2]
x2,x3 integer -> integers:=[2,3]
x1,x3 integer -> integers:=[1,3]
x3 integer -> integers:=[3]

Last the point I wanted to make was that for >= constraint we do not actually need to add an artificial variable at all since we use dual simplex, we either multiply constraint by -1 and add slack or add negative slack, which is the same thing because you still have to multiply the row by -1 to make the column 'canonical'. Thus for ">=" constraint giving input of negative slack for initial bv is fine if we pivot on it or multiply the row by -1 as the 'pivot' operation.

I will look at the rest of the changes a bit later. My main concern is that it could limit the number of ways the user can input a system and get to the same solution. simplex_core is flexible in how the constraints are ordered.