Simplex implementation with A,b,c matrices

Specific Domains Optimization (Mathematical)
1

Hello,

I would like to solve an LP

min cx
s.t. Ax = b

for which I have A, b and c all prepared. That is, I don’t want to go through a modeling phase. Is there a way to define a JuMP model directly with these components ?

2

I suppose you also want to impose some more assumptions here, in particular something like x >= 0, don’t you?

3

I think your best bet now would be to look at https://github.com/jump-dev/MatrixOptInterface.jl

3 Likes
4

You can do it with https://github.com/JuliaSmoothOptimizers/QuadraticModels.jl. Simply specify a zero Hessian (I opened an issue to add a convenience constructor for linear optimization). We currently have interfaces to Xpress (https://github.com/JuliaSmoothOptimizers/QuadraticModelsXpress.jl), CPLEX (https://github.com/JuliaSmoothOptimizers/QuadraticModelsCPLEX.jl) and Gurobi (https://github.com/JuliaSmoothOptimizers/QuadraticModelsGurobi.jl) with more coming. Only the barrier solvers are activated for now though. It should be easy to add the option to use simplex.

For an entirely free solver that is competitive with Gurobi, you can use RipQP (https://github.com/JuliaSmoothOptimizers/RipQP.jl). It’s also an interior-point method.

2 Likes
5

Okay thank you all for your suggestions! I’ll have a look at all this.

6

For solving a model in the standard form, you don’t need a special syntax but you do need to know slack/surplus variables to interpret the solution. Here is how I would solve a LP in the standard form.

using JuMP, Clp
C =[-2.0,3.0,0.0, 0.0]
A=[1.0 1.0 1.0 0.0;
1.0 -1.0 0.0 1.0]
b= [4.0,6.0]
model = Model(Clp.Optimizer)
set_optimizer_attribute(model,"SolveType",1) # SolveType 1 is for primal simplex
@variable(model,x[1:4]>=0)
@objective(model,Min,C'*x)
@constraint(model,A*x.==b)
optimize!(model)
value.(x)

Use print(model) to see the model you are solving:

julia> print(model)
Min -2 x[1] + 3 x[2]
Subject to
 x[1] + x[2] + x[3] == 4.0
 x[1] - x[2] + x[4] == 6.0
 x[1] >= 0.0
 x[2] >= 0.0
 x[3] >= 0.0
 x[4] >= 0.0

To define the same model in JuMP, I would use:

using JuMP, Clp
model = Model(Clp.Optimizer)
set_optimizer_attribute(model,"SolveType",1)
@variable(model,x[1:2]>=0)
@objective(model,Min,-2*x[1]+3*x[2])
@constraint(model,con_1,sum(x[i] for i in 1:2) <=4)
@constraint(model,con_2,x[1] - x[2] <=6)
optimize!(model)
value.(x)

Now use print(model) and compare with the standard form

julia> print(model)
Min -2 x[1] + 3 x[2]
Subject to
 con_1 : x[1] + x[2] <= 4.0
 con_2 : x[1] - x[2] <= 6.0
 x[1] >= 0.0
 x[2] >= 0.0
3 Likes