Simplex solver

Specific Domains Optimization (Mathematical)
,
1

I have just completed an operations research subject in which I was taught the simplex method and a foundation programming subject in which I was taught JavaScript/HTML. During these subjects, I wrote this webpage (source: fusion809/simplex) that solves linear programming problems using the simplex method. It also includes several advanced features that JuMP doesn’t offer (e.g. it shows alternate solutions, it mentions whether the solution is permanently degenerate, whether the problem is infeasible or unbounded, it can also perform more sensitivity analysis than JuMP supports and it shows detailed working for each iteration of simplex used). I was thinking about implementing a Julia equivalent. Partly because that webpage is very poor in performance (e.g. if you solve the default problem the webpage is set to solve it’ll likely take over 1 second), and I wonder whether I can implement a solver in Julia that is higher performance.

Before I begin, I have a couple of questions I’m hoping you folks can help answer for me.

  1. What are some ways I could display tableaux and row operations in Julia? The most obvious way to me, at least, would be to write the output to a markup file (e.g. TeX, Asciidoc, HTML) and use the table formatting of that markup format to generate the tableaux and whatever other formatting is available for displaying the row operations, but I’m wondering whether there are other ways.

  2. Does a solver like this already exist in Julia? (That is same features, shows detailed working, supports detailed sensitivity analysis, etc.) I have searched for myself and failed to find one, but I thought I’d double check before proceeding.

4 Likes
2

Here are some implementations of simplex algorithms in Julia. Some of them are no longer maintained and might only work for older versions of Julia:

1 Like
3

Thanks for your efforts. I was aware there were some simplex solvers written in Julia, I should have clarified that what I meant was simplex solvers with similar features to mine. The ones I had found did not have these features.

4

JuMP is an AML that provides an interface to several solvers both open-source and commercial.

You can query the termination status, e.g. termination_status(model)= MOI.INFEASIBLE
termination_status(model)=INFEASIBLE_OR_UNBOUNDED

See documentation: https://jump.dev/JuMP.jl/stable/solutions/#Termination-statuses-1

Multiple solutions can be returned depending upon if the solver supports it: https://jump.dev/JuMP.jl/stable/solutions/#Multiple-solutions-1

Sensitivity analysis: https://jump.dev/JuMP.jl/stable/solutions/#Sensitivity-analysis-for-LP-1

From what you have described, it seems like you are after a toy solver that will display each pivoting operation. I am not aware of any such solver in Julia that is publicly available, but possibly someone may have coded one for teaching purposes.

1 Like
5

Thanks. I was aware that some solvers support multiple solutions, but given the free ones don’t I don’t really count it. Likewise sensitivity analysis for JuMP is somewhat limited. It allows you to adjust the RHS side of the constraints and the objective function coefficients. Mine allows you to adjust these and:

  • The constraint coefficients.
  • Add new variable(s).
  • Add new constraint(s).

I will admit, I did not realize one could determine whether the problem was infeasible or unbounded with JUMP, so thanks for correcting me there.

6

You can do all of this in JuMP, but it requires basic expertise in Julia and JuMP.
To change coefficients of constraints, you can wrap the model into a function and then use a loop that builds function for different sets of data before calling optimize!. Check a similar question here

You can add new variables and constraints to a model. Check the example given in the documentation:
https://jump.dev/JuMP.jl/stable/variables/

function add_component_to_model(model::JuMP.Model)
    x = model[:x]
    # ... code that uses x
end
function build_model()
    model = Model()
    @variable(model, x)
    add_component_to_model(model)
end
2 Likes
7

Surprising that I didn’t see this mentioned in the docs. But thanks for clarifying that.