5
$\begingroup$

I am using Julia's JuMP package to solve a cutting-plane method. Namely, I solve a sub-problem, find the most-violated constraint in the master problem, add that to the sub-problem and reoptimize.

My main problem is an exponential cone problem and I am using MOSEK to solve it. I don't know if it helps, but I am also solving the dual problem by using the Dualization package:

model = Model(dual_optimizer(MosekTools.Optimizer))

My question is following: I am only defining the model once, and in each iteration I am adding only one constraint and optimizing the model again. Is it possible that, despite this, JuMP is solving the optimization problem from scratch each time? I am worried because the solver times increase drastically by time.

If there is an option for using the previous solution (not just the optimal solution) in the next optimization stage? I had a look at JuMP tutorials (e.g., Column generation), and even there it looks like they are just optimize! ing again.

$\endgroup$
8
  • 2
    $\begingroup$ Come and post this on the JuMP community forum: discourse.julialang.org/c/domain/opt/13. I don't know if many JuMP folks hang out here. $\endgroup$ Apr 30, 2022 at 20:16
  • 1
    $\begingroup$ There's a least two of us :) $\endgroup$
    – mtanneau
    Apr 30, 2022 at 22:34
  • 1
    $\begingroup$ Three! But in principle, I think it's worth investing in the amount of JuMP content on OR SE, both as a Julia enthusiast and a user of this site $\endgroup$
    – Max
    May 1, 2022 at 3:20
  • 1
    $\begingroup$ Your explicit dualization is likely to do no good. Since Mosek has an automatic dualizer that works for all problems types except SDPs. $\endgroup$ May 2, 2022 at 5:30
  • 1
    $\begingroup$ We did not create the JuMP interface so do not know much about it. Here groups.google.com/g/yalmip/c/rpbAtOZW38I/m/J9ZtSyVkCAAJ is a spectacular case where Yalmip does way better than JuMP. I suggest you post in JuMP specific forum about the issues you are having. Btw I would use Mosek directly if I really care about performance since it would much easier to understand what is going on. $\endgroup$ May 2, 2022 at 13:37

2 Answers 2

12
$\begingroup$

Your question has a two-part answer: how JuMP handles successive solves, and how the solvers handle successive solves.

How JuMP handles successive solves

Recall that JuMP is a modeling layer, not an optimization solver. Therefore, when you build a problem in JuMP and then call optimize!(model), what JuMP does is it passes the model to the underlying solver, then calls that solver's API to solve the model and retrieve the solution.

Thus, let's assume a workflow like build the model, solve, get the solution, add one or more constraints, solve again, get the solution add one or more constraints, solve again, get the solution, add one or more constraints, etc.

What happens under the hood is the following:

  • build the model
  • call solver XXXX API to pass the model and solve it
  • call solver XXXX API to retrieve the solution
  • call solver XXXX API to add one or more constraints
  • call solver XXXX API to solve the model
  • call solver XXXX API to retrieve the solution
  • etc...

There is nothing in JuMP's optimize! function that does something specific in the case where "I have just solved a very similar version of the problem": this is handled by the solver.

Side note: by default, JuMP caches the model in JuMP-owned data structures before passing it to the solver when the user calls optimize!, which may prevent incremental solves. To bypass this and hook into the solver's API directly, use direct mode. (if you have more questions on this, I would recommend you ask them on the Julia discourse forum as linked by odow)

How solvers handle successive solves

TLDR: it's solver-dependent. Some are able to re-use previous information, some aren't.

In the case of Mosek and nonlinear problems: Mosek will solve nonlinear conic problems with its interior-point algorithm. This algorithm is not able to warm-start, and as far as I know, Mosek's API does not permit to pass a warm-start solution anyway. They may do something smart internally, but it's not documented and the user probably has no control over it.

This is a limitation of interior-point algorithms, not Mosek as a software. An alternative is to use a first-order solver such as SCS or COSMO (see the supported solvers in JuMP), which support warm-starts. However, they are first-order methods and may not give you the same precision as interior-point solvers.

$\endgroup$
3
$\begingroup$

I am not familiar with Julia, but you can search for callback and lazycut which allows you to add cutting plane in the optimization process.

For example this link:

https://jump.dev/JuMP.jl/stable/manual/callbacks/

Unfortunately, as you can find on this page, this is not supported for MOSEK by JuMP.

$\endgroup$
1
  • $\begingroup$ Thanks for your answer. Not only does it not work with MOSEK, but also this is for integer programming it seems. $\endgroup$ Apr 30, 2022 at 14:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.