Simplex Algorithm
11-20-2023, 07:52 PM (This post was last modified: 11-20-2023 08:35 PM by ftneek.)
Post: #37
 ftneek Member Posts: 83 Joined: Oct 2022
RE: Simplex Algorithm
(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.

- neek
 « Next Oldest | Next Newest »

 Messages In This Thread Simplex Algorithm - ftneek - 11-11-2023, 11:21 PM RE: Simplex Algorithm - Albert Chan - 11-11-2023, 11:51 PM RE: Simplex Algorithm - Albert Chan - 11-12-2023, 12:38 AM RE: Simplex Algorithm - Albert Chan - 11-12-2023, 05:11 PM RE: Simplex Algorithm - ftneek - 11-12-2023, 05:40 PM RE: Simplex Algorithm - Albert Chan - 11-13-2023, 02:48 PM RE: Simplex Algorithm - ftneek - 11-12-2023, 12:00 AM RE: Simplex Algorithm - ftneek - 11-12-2023, 01:44 AM RE: Simplex Algorithm - Albert Chan - 11-12-2023, 11:04 PM RE: Simplex Algorithm - ftneek - 11-13-2023, 01:51 AM RE: Simplex Algorithm - Albert Chan - 11-12-2023, 08:46 PM RE: Simplex Algorithm - ftneek - 11-12-2023, 10:09 PM RE: Simplex Algorithm - ftneek - 11-13-2023, 05:34 PM RE: Simplex Algorithm - Albert Chan - 11-13-2023, 10:46 PM RE: Simplex Algorithm - Albert Chan - 11-14-2023, 02:25 AM RE: Simplex Algorithm - ftneek - 11-14-2023, 06:24 AM RE: Simplex Algorithm - Albert Chan - 11-14-2023, 09:23 AM RE: Simplex Algorithm - ftneek - 11-14-2023, 10:39 AM RE: Simplex Algorithm - Albert Chan - 11-15-2023, 04:36 PM RE: Simplex Algorithm - ftneek - 11-15-2023, 05:58 PM RE: Simplex Algorithm - Albert Chan - 11-16-2023, 11:42 AM RE: Simplex Algorithm - Albert Chan - 11-16-2023, 07:15 PM RE: Simplex Algorithm - ftneek - 11-17-2023, 07:47 AM RE: Simplex Algorithm - Albert Chan - 11-17-2023, 11:04 AM RE: Simplex Algorithm - ftneek - 11-18-2023, 01:27 AM RE: Simplex Algorithm - ftneek - 11-18-2023, 10:31 PM RE: Simplex Algorithm - Albert Chan - 11-19-2023, 12:57 AM RE: Simplex Algorithm - ftneek - 11-19-2023, 07:05 AM RE: Simplex Algorithm - Albert Chan - 11-19-2023, 04:58 PM RE: Simplex Algorithm - Albert Chan - 11-20-2023, 06:12 PM RE: Simplex Algorithm - ftneek - 11-21-2023, 08:36 AM RE: Simplex Algorithm - Albert Chan - 11-21-2023, 02:05 PM RE: Simplex Algorithm - ftneek - 11-19-2023, 08:02 PM RE: Simplex Algorithm - ftneek - 11-20-2023, 12:18 AM RE: Simplex Algorithm - Albert Chan - 11-20-2023, 02:14 AM RE: Simplex Algorithm - ftneek - 11-20-2023, 09:02 AM RE: Simplex Algorithm - Albert Chan - 11-20-2023, 11:42 AM RE: Simplex Algorithm - Albert Chan - 11-20-2023, 03:34 PM RE: Simplex Algorithm - ftneek - 11-20-2023 07:52 PM RE: Simplex Algorithm - Albert Chan - 11-21-2023, 05:58 PM RE: Simplex Algorithm - Albert Chan - 11-21-2023, 11:20 PM RE: Simplex Algorithm - Albert Chan - 11-22-2023, 06:44 PM RE: Simplex Algorithm - Albert Chan - 11-22-2023, 10:10 PM RE: Simplex Algorithm - Albert Chan - 12-24-2023, 03:46 PM RE: Simplex Algorithm - ftneek - 12-24-2023, 07:32 PM RE: Simplex Algorithm - Albert Chan - 12-24-2023, 08:05 PM RE: Simplex Algorithm - ftneek - 11-23-2023, 01:23 AM RE: Simplex Algorithm - Albert Chan - 11-23-2023, 06:35 AM RE: Simplex Algorithm - ftneek - 12-22-2023, 07:38 AM RE: Simplex Algorithm - Albert Chan - 12-22-2023, 04:07 PM RE: Simplex Algorithm - ftneek - 12-22-2023, 07:28 PM RE: Simplex Algorithm - Albert Chan - 12-23-2023, 04:44 AM RE: Simplex Algorithm - ftneek - 12-23-2023, 07:46 AM RE: Simplex Algorithm - Albert Chan - 12-23-2023, 10:23 AM RE: Simplex Algorithm - ftneek - 12-23-2023, 09:30 PM RE: Simplex Algorithm - ftneek - 01-07-2024, 02:40 AM

User(s) browsing this thread: 1 Guest(s)