Difficulty to understand the JuMP problem setting

Specific Domains Optimization (Mathematical)
1

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.

2

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?

3

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
4

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
5

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
6

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
7

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?

8

I am trying to rearrange karatekas in the below graph:

818Ă—585 31.5 KB

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

9

This is a graph layout problem: Graph drawing - Wikipedia. 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
10

Actually, GitHub - JuliaGraphs/GraphPlot.jl: Graph visualization for Julia. might be in better shape for Julia 1.0.

11

https://github.com/JuliaGraphs/GraphPlot.jl/pull/75

12

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

optimal_karate
optimal_karate1330Ă—1064 185 KB

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

13

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…

14

Really addictive game.