Solving a cplex model via JuMP and java

Specific Domains Optimization (Mathematical)
1

A colleague and I both implemented a model we have been working on, him using a java interface to cplex and me using JuMP. After spending some time to reconcile the .lp outputs of the two models I genuinely believe that the constraints imposed by both models are identical yet the solve time in the JuMP interface is painfully slower in comparison to via java. Whereas the java model completes in ~2s, I terminated the julia model after some minutes.

Is there an explanation for this and, more importantly, is there anything I can do to close the gap? Below I attach the cplex initialisation in both models. FWIW the number of binaries is much /higher/ in the java model yet it runs much faster.

Thanks.

Java
Default row names c1, c2 ... being created.
CPXPARAM_Threads                                 1
CPXPARAM_Parallel                                1
CPXPARAM_TimeLimit                               3600
CPXPARAM_WorkMem                                 4000
CPXPARAM_MIP_Limits_TreeMemory                   4000
Tried aggregator 2 times.
MIP Presolve eliminated 12710 rows and 318 columns.
MIP Presolve modified 1317 coefficients.
Aggregator did 1 substitutions.
Reduced MIP has 7191 rows, 782 columns, and 22798 nonzeros.
Reduced MIP has 758 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.05 sec. (41.23 ticks)
Found incumbent of value 0.000000 after 0.08 sec. (67.89 ticks)
Probing time = 0.01 sec. (8.78 ticks)
Tried aggregator 1 time.
Reduced MIP has 7191 rows, 782 columns, and 22798 nonzeros.
Reduced MIP has 758 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.02 sec. (14.47 ticks)
Probing time = 0.01 sec. (8.72 ticks)
Clique table members: 11519.
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: none, using 1 thread.
JuMP
CPXPARAM_Threads                                 1
Tried aggregator 2 times.
MIP Presolve eliminated 427 rows and 16 columns.
MIP Presolve modified 376 coefficients.
Aggregator did 2 substitutions.
Reduced MIP has 7178 rows, 782 columns, and 21678 nonzeros.
Reduced MIP has 286 binaries, 24 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.02 sec. (15.84 ticks)
Probing fixed 0 vars, tightened 80 bounds.
Probing time = 0.02 sec. (18.38 ticks)
Tried aggregator 1 time.
MIP Presolve modified 36 coefficients.
Reduced MIP has 7178 rows, 782 columns, and 21670 nonzeros.
Reduced MIP has 288 binaries, 47 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.01 sec. (9.49 ticks)
Probing time = 0.00 sec. (3.85 ticks)
2

Are you testing the same model in both cases? Itā€™s not that their goals are identical, but really if they have the same variables, same constraints. That would be a very easy explanation.

Some models tend to perform very well (the root relaxation is very close to the integer optimum value, for instance), others very poorly (poor choice of big-M values, even though solvers like CPLEX or Gurobi can improve them on the fly).

Otherwise, even if you are solving the exact same thing, CPLEX uses randomness at some point to perform its branch-and-bound process, you sometimes get lucky, some others not.

3

Well, I believe the two formulations are equivalent. As I said, I spent some time to massage my JuMP .lp format into his java .lp format and then compared all constraints. They seemed exactly the same to me.

I imposed some limits on some integer variables that he didnā€™t but other than that the same constraints were implemented and me constraining the range of some integers should only help me, right? I could remove those limits and Iā€™m sure i wouldnā€™t change the broad result.

Only one technicality niggles me though: my colleague , to simplify his java implementation, introduced a set of variables, z_ij, indexed by 1 <= i,j <= n eventhough only the lower triangle were of use. Later he constrained the row sums of the UT to be 0. In my comparison I assumed that the presolver would eliminate all constraints that referred to ā€œfalseā€ z variables.

4

Well, I believe the two formulations are equivalent.

What weā€™re looking for are identical formulations, not just equivalent. If you can create identical (not just equivalent) models and the solution time issue is still present, then that is something to look into.

5

The two following links are (respectively) the outputs of the java and jump programs on P3, a 4-vertex, 3-edge graph, java-p3.lp - Pastebin.com and jump-p3.lp - Pastebin.com. I believe these two models to be identical. The java program uses 0-based indexing so a jump variable y[(1, 2)] maps to the java variable ye_1_0 (source and dest reordered :frowning: ).

The perl script [here] will massage both .lp files into a common format that can be compared more easily when filtered through ā€˜sortā€™.
(massage.pl - Pastebin.com)

Thanks.

6

How did you write out the JuMP LP? It is corrupted (e.g., line 97 c19: == 0), and the names arenā€™t valid LP names. Did you use MathOptFormat? The latest version?

If you have identical models, does the JuMP version still take longer? Does it take longer to build or longer to solve?

7

Thanks for all of the help and suggestions. Yes, I had been using an older version of MathOptFormat to write to the .lp file. Now that I have upgraded to JuMP v0.19.2 and MathOptFormat v0.1.1 when I call

        # https://github.com/odow/MathOptFormat.jl
        lp_model = MathOptFormat.LP.Model()
        MOI.copy_to(lp_model, backend(m))
        MOI.write_to_file(lp_model, "model.lp")

I get a .lp file that is immediately loadable into the cplex solver/interpreter that is run from the shell prompt. However, there is a huge disparity in running times between running the model via a call in julia to

optimize!(m)

and loading the above generated model.lp file into teh cplex interpreter and solving there. The difference is on the order of 29s when cplex is called from the julia program vs. 0.2s when solving the model directly in the cplex solver for the instance I have been looking at.

I have no idea what goes in in the optimize!() call. Iā€™m presuming itā€™s more than simply spawning off a cplex process and it running autonomously.

Performing the same comparison with the java interface to cplex vs. the .lp file written by it yields almost no difference: ~0.17s in both cases.

8

What happens if you use direct mode?

using JuMP, CPLEX

# Try:
model_direct = JuMP.direct_model(CPLEX.Optimizer())

# and also:
model_auto = JuMP.Model(with_optimizer(CPLEX.Optimizer))
9

Running it in this way gives a run time of ~8s as against the auto mode you suggest which has a run time of ~32s. One nice thing about the latter is that I can write the model to a .lp file for inspection although it may be possible in the former, too.

I am fearing that while I have verified the constraints to be identical in both the java and JuMP models my colleague may have differed from me in which variables were binary, int, general, etc. Looking at the CPLEX pre-solve information I see differing numbers of, say, Clique table members, and this must relate to the types of variables. I need to look at this and I apologise if it means that I have wasted your time on this ā€œproblem.ā€

10

I believe you should trust the output you got:

Presolve time = 0.02 sec. (15.84 ticks)
Probing time = 0.02 sec. (18.38 ticks)
Presolve time = 0.01 sec. (9.49 ticks)
Probing time = 0.00 sec. (3.85 ticks)

If you @time the whole process and it took longer than CPLEX told you, that might be the compilation time. The first call to optimize!() take some time, 32s seems a bit odd but 8s should be that. Since you have an .lp from Java you can read it in JuMP to solve exactly the same problem.

Anyway, before solving anything useful, I suggest you solve a trivial problem with CPLEX to avoid any compilation time.

Iā€™ll do some tests too with the .lp you gave but I need to access a computer with CPLEX before.

11

I have come to the conclusion that the huge disparity is down to the variable types. I was satisfied that both sets of constraints were identical but the models still differed: some variables were declared as integer when they could have been declared as binary. When I aligned my variable types with the java implementation I got similar solve times.

Thanks for the interest and suggestions.

1 Like