Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Incorrect algorithm #1

Closed
apirobot opened this Issue Mar 28, 2017 · 2 comments

Comments

Projects
None yet
2 participants
@apirobot
Copy link

apirobot commented Mar 28, 2017

I think this algorithm doesn't work properly. For example, for this data:

F = 300x1 + 250x2 + 450x3 --> max
15
x1 + 20x2 + 25x3 <= 1200
35x1 + 60x2 + 60x3 <= 3000
20
x1 + 30x2 + 25x3 <= 1500
250*x2 >= 500
x >= 0

Returns: [(0, 12.0), (2, 180.0), (4, 60.0)], 23400.0

But the answer should be:
F = 23060
x1 = 56, x2 = 2, x3 = 12.8
1

Also, I've checked some other data. And for this data, it doesn't work at all.

@j2kun

This comment has been minimized.

Copy link
Owner

j2kun commented Apr 21, 2018

The code indeed does not solve this correctly. I don't yet have a fix.

From what I can see, variable x2 is never pivoted. After inspecting the pivot choices (which are heuristics), I believe the pivot rules are to blame. I previously thought that improving "any" improvable column would work, but this is apparently incorrect. The solution that was reported (but had an indexing bug) was x1 = 60, x2=0, x3 = 12. This is obviously wrong because of the constraint that x2 >= 2.

If I force the code to first pivot on the tableau entry (1,1), then I let it solve to completion as using a better pivot choice heuristic (max of bottom row, min quotient), I get the right output:

[3.333333333333332, 0.0, 5.0, 1.0, -0.3333333333333333, 0.0, 0.0, 200.0]
[0.5833333333333334, 1.0, 1.0, 0.0, 0.016666666666666666, 0.0, 0.0, 50.0]
[2.5, 0.0, -5.0, 0.0, -0.5, 1.0, 0.0, 0.0]
[-145.83333333333334, 0.0, -250.0, 0.0, -4.166666666666667, 0.0, -1.0, -12000.0]
[154.16666666666666, 0.0, 200.0, 0.0, -4.166666666666667, 0.0, 0.0, -12500.0]
Next pivot index is=0,2 

Tableau after pivot:
[0.6666666666666664, 0.0, 1.0, 0.2, -0.06666666666666667, 0.0, 0.0, 40.0]
[-0.08333333333333304, 1.0, 0.0, -0.2, 0.08333333333333333, 0.0, 0.0, 10.0]
[5.833333333333332, 0.0, 0.0, 1.0, -0.8333333333333333, 1.0, 0.0, 200.0]
[20.833333333333258, 0.0, 0.0, 50.0, -20.833333333333336, 0.0, -1.0, -2000.0]
[20.83333333333337, 0.0, 0.0, -40.0, 9.166666666666668, 0.0, 0.0, -20500.0]

Next pivot index is=3,0 

Tableau after pivot:
[0.0, 0.0, 1.0, -1.4000000000000052, 0.6000000000000023, 0.0, 0.032000000000000105, 104.00000000000021]
[0.0, 1.0, 0.0, 0.0, -2.7755575615628914e-17, 0.0, -0.004, 1.9999999999999982]
[0.0, 0.0, 0.0, -13.000000000000048, 5.000000000000021, 1.0, 0.28000000000000097, 760.0000000000019]
[1.0, 0.0, 0.0, 2.400000000000009, -1.0000000000000038, 0.0, -0.048000000000000174, -96.00000000000036]
[0.0, 0.0, 0.0, -90.00000000000028, 30.000000000000117, 0.0, 1.0000000000000056, -18499.99999999999]

Next pivot index is=2,4 

Tableau after pivot:
[0.0, 0.0, 1.0, 0.1599999999999997, 0.0, -0.11999999999999995, -0.0015999999999999973, 12.800000000000011]
[0.0, 1.0, 0.0, -7.216449660063513e-17, 0.0, 5.551115123125759e-18, -0.003999999999999998, 2.000000000000002]
[0.0, 0.0, 0.0, -2.5999999999999983, 1.0, 0.19999999999999915, 0.05599999999999995, 151.99999999999974]
[1.0, 0.0, 0.0, -0.1999999999999993, 0.0, 0.1999999999999999, 0.007999999999999986, 55.99999999999996]
[0.0, 0.0, 0.0, -12.000000000000028, 0.0, -5.999999999999998, -0.6799999999999995, -23060.0]

Up to rounding error, you can see x3=12.8, x2=2, x1=56.

However, even with the updated pivot selection rule, the first chosen pivot is not (1,1). I will have to think more on this.

@j2kun

This comment has been minimized.

Copy link
Owner

j2kun commented Apr 21, 2018

Ah, I should be selecting the column according to the minimum positive entry in the last row. Fixing.

@j2kun j2kun closed this Apr 21, 2018

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.
You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session.