(Mathematica) Sparse, Modified-Simplex Linear Programming
- or -
Post a project like this£600(approx. $752)
- Posted:
- Proposals: 1
- Remote
- #43871
- Expired
Description
Experience Level: Expert
I require the solution to a large linear programming problem via a modified Simplex method that uses sparse matrix notation.
You should have fluency in Linear Programming /Simplex algorithms, hopefully having done projects like this before.
Background
The problem is large with almost 8000 constraints, almost 160,000 variables, and nearly a million initial coefficients. I know that a corner solution will be integer. I do NOT have an estimate of how many coefficients the matrix might grow.
I imagine performing the solution in Mathematica (in Windows), but am open to other platforms. Mathematica\'s LP solutions are either sparse or simplex but not both. Essentially, when running a large sparse LP, Mathematica uses interior point methods that will not guarantee (and don\'t provide in practice) a corner point. On the other hand, the Simplex method that would give a corner point does not support sparse matrices.
Requirements:
To create a program to receive a sparse matrix with the above size, objective function and right-hand side to the problem and then solve the LP problem via the simplex method (with three modification, below) while NOT expanding the problem, rather keeping it in sparse form. All equations will be equalities.
The modifications to the simplex method follows:
Reason for modification
The method will capitalize on the fact that many (but not all) of the equations have coefficients of 0, 1 and -1, and the RHS is 0. In the standard Simplex method, when going down the entering variable’s column to find a new pivot, if such a row as above has a “1” coefficient in the column being checked, then that row would dictate that the new value of the entering variable would be 0. However, if that row were multiplied by -1 (changing the “1” to “-1” for that row in the column being tested), then that row would not affect the new amount of the entering variable. This would greatly speed up the run-time since it is much more likely that each iteration yields an increase in the overall objective (eliminating many “zero” iterations.)
A further speed-up is made by requiring entering variables to have a new value that would be non-zero.
Actual Modifications:
First Change:
In the standard Simplex method, the entering variable is chosen by looking at the objective function and choosing a variable with the most negative coefficient.
In this version, this test will be used, BUT if the new value of the entering variable would be zero, then this variable is rejected and the next variable with the by the objective function rule is tested. To be clear, if the new value of the supposed entering variable would be zero, then no row operations are performed. (This will require tracking entering variables that have been rejected.) So, each iteration of this modified Simplex would likely require performing the ratio of RHS-to-coefficient for many columns before an acceptable entering value is found.
Second Change:
When testing a potential entering variable, just as in the standard Simplex, the potential pivot is searched for by comparing the ratio of the RHS to the Positive coefficients in the column (for non-zero coefficients). When testing each row by row, the program will use the sparse matrix to ONLY check nonzero elements in the row. No Looping through zero coefficients should take place. It is not enough to do an “if zero…skip” logic, since this test would use a lot of run time. The program must use the sparse matrix form to “grab only the nonzero coefficients” and loop through these only.
Third and last change from Simplex
1) When checking these nonzero column elements (in the potential entering variable’s column),
a) if the coefficient is negative, no change is made to the Simplex method (i.e., this rows is not the pivot and does not affect the new value of the entering variable).
b) if the coefficient is positive AND the RHS for that row is NOT zero, no change is made to the Simplex method (i.e., this rows MAY BE the pivot and the ratio of RHS to coefficient is an upper limit on the new value of the entering variable). The row with the lowest ratio (or one of them with a tied value) defines the pivot element (or to be precise, potential pivot, since this potential entering variable may be eliminated as an actual entering variable).
c) if the coefficient is POSITIVE AND the RHS for that row is EQUAL TO ZERO, the algorithm is changed by considering this rows AS-IF it were multiplied by -1, (i.e., this rows is not the pivot and does not affect the new value of the entering variable). Essentially this means that any row with a RHS = Zero is skipped when looking for a pivot and determining the new value of the potential entering variable. NOTE, while searching through for the pivot and the new entering variable’s value, no row operations are done – the above “AS-IF … multiplied by -1” is only a justification for eliminating the row from considerations. (However, see 2a below.)
2) If a potential entering variable using the above criteria would have a new value that is greater than zero (and would thus increase the objective function), then this potential entering variable becomes and actual entering variable. In this case, the normal Simplex method row operations take place, with the following change:
a) In the case that a potential entering variable is accepted as an actual entering variable, all the “AS-IF … multiplied by -1” (from 1c) situation must actually be done. The specific change is as follows, when clearing out all non-pivot elements in the entering variable’s column to be zero, if BOTH the coefficient in the column is POSITIVE AND RHS is zero, then multiply that entire row by -1 before proceeding. To clarify this affects more coefficients than in the entering variable’s column.
You should have fluency in Linear Programming /Simplex algorithms, hopefully having done projects like this before.
Background
The problem is large with almost 8000 constraints, almost 160,000 variables, and nearly a million initial coefficients. I know that a corner solution will be integer. I do NOT have an estimate of how many coefficients the matrix might grow.
I imagine performing the solution in Mathematica (in Windows), but am open to other platforms. Mathematica\'s LP solutions are either sparse or simplex but not both. Essentially, when running a large sparse LP, Mathematica uses interior point methods that will not guarantee (and don\'t provide in practice) a corner point. On the other hand, the Simplex method that would give a corner point does not support sparse matrices.
Requirements:
To create a program to receive a sparse matrix with the above size, objective function and right-hand side to the problem and then solve the LP problem via the simplex method (with three modification, below) while NOT expanding the problem, rather keeping it in sparse form. All equations will be equalities.
The modifications to the simplex method follows:
Reason for modification
The method will capitalize on the fact that many (but not all) of the equations have coefficients of 0, 1 and -1, and the RHS is 0. In the standard Simplex method, when going down the entering variable’s column to find a new pivot, if such a row as above has a “1” coefficient in the column being checked, then that row would dictate that the new value of the entering variable would be 0. However, if that row were multiplied by -1 (changing the “1” to “-1” for that row in the column being tested), then that row would not affect the new amount of the entering variable. This would greatly speed up the run-time since it is much more likely that each iteration yields an increase in the overall objective (eliminating many “zero” iterations.)
A further speed-up is made by requiring entering variables to have a new value that would be non-zero.
Actual Modifications:
First Change:
In the standard Simplex method, the entering variable is chosen by looking at the objective function and choosing a variable with the most negative coefficient.
In this version, this test will be used, BUT if the new value of the entering variable would be zero, then this variable is rejected and the next variable with the by the objective function rule is tested. To be clear, if the new value of the supposed entering variable would be zero, then no row operations are performed. (This will require tracking entering variables that have been rejected.) So, each iteration of this modified Simplex would likely require performing the ratio of RHS-to-coefficient for many columns before an acceptable entering value is found.
Second Change:
When testing a potential entering variable, just as in the standard Simplex, the potential pivot is searched for by comparing the ratio of the RHS to the Positive coefficients in the column (for non-zero coefficients). When testing each row by row, the program will use the sparse matrix to ONLY check nonzero elements in the row. No Looping through zero coefficients should take place. It is not enough to do an “if zero…skip” logic, since this test would use a lot of run time. The program must use the sparse matrix form to “grab only the nonzero coefficients” and loop through these only.
Third and last change from Simplex
1) When checking these nonzero column elements (in the potential entering variable’s column),
a) if the coefficient is negative, no change is made to the Simplex method (i.e., this rows is not the pivot and does not affect the new value of the entering variable).
b) if the coefficient is positive AND the RHS for that row is NOT zero, no change is made to the Simplex method (i.e., this rows MAY BE the pivot and the ratio of RHS to coefficient is an upper limit on the new value of the entering variable). The row with the lowest ratio (or one of them with a tied value) defines the pivot element (or to be precise, potential pivot, since this potential entering variable may be eliminated as an actual entering variable).
c) if the coefficient is POSITIVE AND the RHS for that row is EQUAL TO ZERO, the algorithm is changed by considering this rows AS-IF it were multiplied by -1, (i.e., this rows is not the pivot and does not affect the new value of the entering variable). Essentially this means that any row with a RHS = Zero is skipped when looking for a pivot and determining the new value of the potential entering variable. NOTE, while searching through for the pivot and the new entering variable’s value, no row operations are done – the above “AS-IF … multiplied by -1” is only a justification for eliminating the row from considerations. (However, see 2a below.)
2) If a potential entering variable using the above criteria would have a new value that is greater than zero (and would thus increase the objective function), then this potential entering variable becomes and actual entering variable. In this case, the normal Simplex method row operations take place, with the following change:
a) In the case that a potential entering variable is accepted as an actual entering variable, all the “AS-IF … multiplied by -1” (from 1c) situation must actually be done. The specific change is as follows, when clearing out all non-pivot elements in the entering variable’s column to be zero, if BOTH the coefficient in the column is POSITIVE AND RHS is zero, then multiply that entire row by -1 before proceeding. To clarify this affects more coefficients than in the entering variable’s column.
Matthew M.
0% (0)Projects Completed
-
Freelancers worked with
-
Projects awarded
0%
Last project
11 May 2024
United Kingdom
New Proposal
Login to your account and send a proposal now to get this project.
Log inClarification Board Ask a Question
-
There are no clarification messages.
We collect cookies to enable the proper functioning and security of our website, and to enhance your experience. By clicking on 'Accept All Cookies', you consent to the use of these cookies. You can change your 'Cookies Settings' at any time. For more information, please read ourCookie Policy
Cookie Settings
Accept All Cookies