Mixed-Integer Programming in Casadi

[Mario Zanon]

Hi,

I am wondering how easy it is to solve a mixed-integer program in casadi. 

I tried to look in the documentation but unfortunately I could not find much about mixed-integer programming within casadi.

My questions are:

- which solvers are interfaced? Of these, is any coming with casadi (like e.g. Ipopt)? Is any open source / free?

- can the power indexing be used also for mixed-integer problems?

[Joel Andersson]

Hi Mario,

Currently interfaced are:

- bonmin (MINLP, free & open-source, distributed with CasADi)

- knitro (MINLP)

- cplex (MIQP, free for academic use)

- gurobi (MIQP, free for academic use)

What do you mean by power indexing?

Joel

[Mario Zanon]

Thanks for the nice answer!

Is there any documentation on how to call these solvers and retrieve the solution?

I thought that power indexing was a casadi-created term. I mean that I'd like to use e.g. V['x',1,0,'position'] in order to index optimisation variables.

Ciao,

Mario

[Joel Andersson]

Ah, I've heard it being called "Joris style".. I don't see why it wouldn't work with it. Although this has a bit fallen out of use after we added support for generalized MX inputs. And note that it is not available for Matlab/Octave.

Here is an MINLP example: https://github.com/casadi/casadi/blob/master/docs/examples/python/lotka_volterra_minlp.py

Just use the normal QP/NLP interface and set the "discrete" option.

Joel

[Mario Zanon]

Thanks again!

Actually I really like Joris style, since it gives me all the freedom to easily index any problem I want in an easy and very efficient way, which eliminates the risk of indexing errors.

Could you please explain better what are generalised MX inputs? From the name I suppose they might be a nice alternative.

About the example you sent, it's nice to see how to formulate MINLPs, but it has the old style indexing, which has caused me more than one headache and billions of bugs. See e.g. the difference between

https://github.com/casadi/casadi/blob/master/docs/examples/python/vdp_collocation.py

and

https://github.com/casadi/casadi/blob/master/docs/examples/python/vdp_collocation2.py

Ciao,

Mario

[Ramon Dalmau]

I am also interested on the generalised MX inputs alternative to Joris style :)

[Joel Andersson]

Hi Mario, Ramon,

Sorry for not being clear enough.

It didn't use to be possible to have a e.g. a vertical concatenation in the input expressions of an MX function, e.g.

# Used to be possible for SX, but not for MX
x = MX.sym('x')
y = MX.sym('y')
f = Function('f', [vertcat(x,y)],[x+y])

Allowing e.g. vertcat(x,y) in the inputs is what I mean by generalized inputs. The old way to do it was to rewrite it as:

# Old syntax, still valid but less efficient and less readable than the above
xy = MX.sym('xy', 2)
[x,y] = vertsplit(xy);
f = Function('f', [xy],[x+y])

The "Joris style" was originally an attempt to facilitate the modeling using the older syntax, without manually having to build up an "xy" vector and splitting up into its components. Because of the generalization of Function to allow combinations of horzcat, reshape, vec and (for vectors only) vertcat, there is less need for "Joris style". You can just keep the expressions in a struct/dict, while at the same time building up a list/cell array which you call vertcat/vcat on when constructing the function.

Joel

[Mario Zanon]

Hi Joel,

I actually missed this answer of yours.

I think I see your point but only partially. Joris style does much more than what you just described (or I missed something). It directly gives you numerical structures corresponding to the symbolic ones and more.

Here you see an extract from some code I am using. I struggle to see how I could get the same ease of implementation without Joris style.

states = struct_symSX( [ 'p', 'v' ])

state_unc = struct_symSX([ entry('X', shapestruct=(states,states)), ])

# This reuses previously defined variables and orders my optimisation variables in a good way

Vars  = struct_symMX([

    (

     entry("x", struct=states,    repeat=[M,N+1]),

     entry("u", struct=controls,  repeat=[M,N]),

     entry("X", struct=state_unc, repeat=[M,N+1]),# type='symm' if I want to impose that the matrix is symmetric

    ),

])

# Upper and lower bounds

lbx  = Vars( -np.inf )

ubx  = Vars(  np.inf )

# Simple way to group constraints

g = struct_MX( [

entry("dyn",expr=dynconstr),

entry("dynX",expr=dynconstrX),

entry("v",expr=velconstr),

])

# Upper and lower bounds on the generic constraints

lbg = g(0)

ubg = g(0)

lbg['v'] = -np.inf

sol = solver(arg)

Vnum = Vars(sol['x'])

gnum = g(nlp([Vnum,Pnum])[1]) # like this I can debug my code very easily!!
print gnum['dyn']

# A trick to store my simulation results in a tidy and easy to use way (could also be replaced by a dictionary)

Sim_s = struct_symMX([

    (

     entry("x",  struct=states,    repeat=[M,nSim+1]),

     entry("u",  struct=controls,  repeat=[M,nSim]),

     entry("X",  struct=state_unc, repeat=[M,nSim+1]),

    ),

])
Sim_data = Sim_s()

By the way, there are some shortcomings in Joris style as well, but I am using it for years now and it's one of the main reasons why I use casadi, as this makes trying out new ideas extremely simple! So far, I have not seen any good alternative to it.

Ciao,

Mario

[Joel Andersson]

We don't plan to remove "Joris style" before we have a good replacement. It's discussed in this issue: https://github.com/casadi/casadi/issues/1388

Joel

[sgros2009]

Hej Joel, 

have you tried to retrieve the multipliers when solving a problem with bonmin / casADi / Matlab? We have some issues here... multipliers are NaN even if the problem is well-posed (I have a Mickey mouse example if needed).

Best,

Sebastien 

[Joel Andersson]

Hey!

Sorry for slow answer.

I don't think I have tried it, and if I did it was probably long ago. Right now, the multipliers are not calculated at all when using bonmin, and it has nothing to do with MATLAB.

There is an option "calc_lam_x" - can you try setting that to true? It will calculate it from the gradient of the Lagrangian. Another workaround could be to pass the solved problem to IPOPT or another solver (with discrete decision variables fixed from bonmin).

Joel