# Difficulty to understand the JuMP problem setting

Here is my MWE of the problem:

``````using JuMP
using Clp
Random.seed!(2017)
xlocs, ylocs = rand(5), rand(5)

function demo_problem(x,y)
counter = 0
for (xx,yy) in zip(x,y)
val = xx - yy

if (val > epsillon)
counter += 1
else
counter += -1
end
end
return counter
end

mm = Model(solver=ClpSolver())
@variable(mm, 0.0 <= x[1:5] <= 1.0)
@variable(mm, 0.0 <= y[1:5] <= 1.0)
@objective(mm, Min, demo_problem(x,y))

MethodError: no method matching isless(::Float64, ::JuMP.GenericAffExpr{Float64,Variable})
Closest candidates are:
isless(::Float64, !Matched::Float64) at float.jl:459
isless(!Matched::Missing, ::Any) at missing.jl:66
isless(::AbstractFloat, !Matched::AbstractFloat) at operators.jl:148
...

Stacktrace:
[1] <(::Float64, ::JuMP.GenericAffExpr{Float64,Variable}) at .\operators.jl:260
[2] >(::JuMP.GenericAffExpr{Float64,Variable}, ::Float64) at .\operators.jl:286
[3] demo_problem(::Array{Variable,1}, ::Array{Variable,1}) at .\In[25]:12
[4] top-level scope at C:\Users\tfr004\.julia\packages\JuMP\Xvn0n\src\macros.jl:859
[5] top-level scope at In[25]:25
``````

In my actual problem, Iâ€™m counting line section intersections with this algorithm: https://www.geeksforgeeks.org/check-if-two-given-line-segments-intersect/ and my idea was to minize the intersections by using JuMP. I am open to any proposals, because the optimization is not my strongest competence.

If you use `ClpSolver`, you are restricted to models of the LP type, where constraints and objective need to be linear. So, you can not supply a user-defined function.

In that case, you should use the `@NLobjective` macro and also use a nonlinear solver, such as `IPOPT`. However, I donâ€™t think your function will work well then either, as it is not differentiable (or continuous)?

Also, you set up `xlocs` and `ylocs` in the beginning, but then never use them again. Is something missing here?

Thanks for the quick reply. I changed to this:

``````using JuMP
using Ipopt
using Random
Random.seed!(2017)
xlocs, ylocs = rand(5), rand(5)

function demo_problem(x,y)
counter = 0
for (xx,yy) in zip(x,y)
val = xx - yy

if (val > zero(val))
counter += 1
else
counter += -1
end
end
return counter
end

mm = Model(solver=IpoptSolver())
@variable(mm, 0.0 <= x[1:5] <= 1.0)
@variable(mm, 0.0 <= y[1:5] <= 1.0)
@NLobjective(mm, Min, demo_problem(x,y))

Unrecognized function "demo_problem" used in nonlinear expression.

Stacktrace:
[1] error(::String) at .\error.jl:33
[2] top-level scope at C:\Users\tfr004\.julia\packages\JuMP\Xvn0n\src\parsenlp.jl:96
[3] top-level scope at C:\Users\tfr004\.julia\packages\JuMP\Xvn0n\src\macros.jl:1310
[4] top-level scope at In[5]:26
``````

Here are the xlocs and ylocs used (just to test the demo_problem):

``````demo_problem(xlocs,ylocs)
1
``````

Rather than using a generic nonlinear solver like Ipopt, I think your problem is very well suited to reformulation as a mixed-integer linear problem (assuming the problem you actually care about also has only linear constraints). It is very similar to the one in this post:

you should be able to use the same reformulation. If you choose to go this route, you can use e.g. CBC (free) or Gurobi (proprietary, free academic license) as your solver.

If you do choose to use a generic nonlinear solver like Ipopt, please read this section of the JuMP documentation: Nonlinear Modeling â€” JuMP -- Julia for Mathematical Optimization 0.18 documentation (you need to register the `demo_problem` function.

1 Like

This is not true, but it doesnâ€™t matter anyway because your original problem wonâ€™t have only linear constraints due to the cross product (`orientation` function), and so the MILP story doesnâ€™t apply. Sorry I hadnâ€™t noticed your link before. Iâ€™d stick to the general nonlinear interface.

1 Like

Sorry, my first reply was not so clear. I was only trying to explain the error message, not actually suggesting to use the nonlinear interface with the function you provide. I donâ€™t think the automatic differentiation packages will be able to handle that.

To expand on what @tkoolen wrote, I think a reformulation of your function is a better strategy (although I donâ€™t have one in mind). Even if it turns out that there are some nonlinear constraints as well as binary variables, there are some MINLP-capable solvers compatible with JuMP out there (e.g. POD, SCIP.

2 Likes

Yeah, but before going that route, itâ€™s probably a good idea to determine what additional constraints there are on the variables. What would forbid a trivial solution with all line segments in parallel, for example?

I am trying to rearrange karatekas in the below graph:

In such an order that intersections of the connecting lines are minimized. Currently I believe that it would produce more beautiful end result.

This is a graph layout problem: https://en.wikipedia.org/wiki/Graph_drawing. Finding a global minimizer, one that achieves the crossing number, is an NP-hard problem. You can try to go the MINLP route as suggested earlier, but it wonâ€™t scale well, is a pretty non-standard way of doing this, and seems like overkill. See the Wikipedia article for a list of heuristic-based algorithms, and https://github.com/IainNZ/GraphLayout.jl for some Julia implementations.

1 Like

Actually, https://github.com/JuliaGraphs/GraphPlot.jl might be in better shape for Julia 1.0.

I donâ€™t believe anymore. Clearly my model is too simple. Here is the optimal result:

I would like to animate the solutions through iterations. How can I get iteration i variable values?

Seeing this reminded me very much of a game where you got given a graph and you were supposed to uncross the lines by moving nodes: https://www.ologames.com/Free_Games/Uncross-The-Lines. Now I have to play it againâ€¦