In http://yetanothermathprogrammingconsultant.blogspot.com/2015/01/the-hostile-brothers-problem-1.html we discussed how to find local optimal solutions for a simple geometric problem. Using a local solver, we use:
where model m2 uses the second (smooth) variant of:
Multi-start Algorithm
A simple multi-start algorithm would just slap a loop around this. Indeed we can find slightly better solutions with this:
obj | min distance | time | |
local solve conopt | 0.01694 | 0.13016 | 1 |
multi start sequential (N=50, conopt) | 0.01744 | 0.13208 | 93 |
multi start sequential (N=50, snopt) | 0.01744 | 0.13205 | 39 |
multi start parallel (N=500, 4 threads, snopt) | 0.01748 | 0.13219 | 113 |
As the problems are independent of each other it is easy to solve them in parallel. Here we used a scheme where we solve four problems in parallel. If a problem is done, a new one is started, so we keep those four threads busy (no starvation). The code managing all this is written in GAMS using a few loops. Being able to write little algorithms in a modeling language can be an important feature. Using the parallel algorithm we can solve 500 problems on 4 worker threads in under 2 minutes.
Local Solver
Interestingly, the heuristic solver “Localsolver” likes the first formulation, model m1, better. This is more compact but non-differentiable. This solver does not care about the objective function not being smooth.
LocalSolver 24.4.1 r50296 Released Dec 20, 2014 WEI x86 64bit/MS Windows LocalSolver 5.0 (Win64, build 20141219) Searching for equations that define variables... found 0 time | iterations | objective Stopped due to time limit. |
For this particular problem the multi-start + local NLP solver seems more efficient.
Next: more experiments.
Update: LocalSolver statistics
The counts for the expressions and operands are not immediately clear. To investigate we use n=3 points. The log file shows:
Instance: 6 Variables |
With an option we can write out an .LSP file with localsolver function code :
.LSP file | My comment |
function model() { | n0,n1: Bounds on each variable n2 := x1 in [0,1] n4 := -x1 n5 := x2 in [0,1] n6 := (-x1) + x2 n7 := (x2-x1)^2 n8 := y1 in [0,1] n9 := -y1 n10 := y2 in [0,1] n11 := (-y1)+y2 n12 := (y2-y1)^2 n13:= (x2-x1)^2+(y2-y1)^2 n30: mindist := min(n13,n22,n29) n31-n33: Related to dummy objective function row n33:= mindist n34: not used? maximize mindist |
Indeed the generated code is very low level. This certainly does not look optimal. Lets say there is room for improvement. I suspect that a smarter code will increase the number of iterations per second only (the search space is related to the number of these float variables which stays the same). Update: see comment below where some experiments show no performance degradation for this code.
I do not understand the number of expressions/operands in the output of LocalSolver. There are 150 variables, so 75 points, so 2775 pairs. For each pair, you need 2 squares, 2 minuses and 1 plus. The square takes 1 operand while the plus/minus takes 2 operands each, resulting in 7 operands per pair. The minimum operator takes 2775 operands. In total I would therefore expect 9*2775 = 13876 operands. What explains the large difference?
ReplyDeleteEven though the GAMS link to LocalSolver generates some not-perfectly-optimal instructions, the LocalSolver presolver seems to take care of shrinking the expressions just fine.
ReplyDeleteI did a small experiment with running a native LocalSolver formulation of this problem against the GAMS formulation on the same machine with 60s timelimit and got pretty much the same result.
The LocalSolver formulation is
function input() {
n = 75;
}
function model() {
x[1..n] <- float(0,1);
y[1..n] <- float(0,1);
obj <- min[i in 2..n][j in 1..i-1](pow(x[i]-x[j],2) + pow(y[i]-y[j],2));
maximize obj;
}
and this is the from the output I get:
LocalSolver 5.0 (Linux64, build 20141120)
Copyright (C) 2014 Innovation 24, Aix-Marseille University, CNRS.
All rights reserved (see Terms and Conditions for details).
...
Model:
expressions = 14029, operands = 30825
decisions = 150, constraints = 0, objectives = 1
Param:
time limit = 60 sec, no iteration limit
seed = 0, nb threads = 1, annealing level = 1
Objectives:
Obj 0: maximize, no bound
Phases:
Phase 0: time limit = 60 sec, no iteration limit, optimized objective = 0
Phase 0:
[0 sec, 0 itr]: obj = (0), mov = 0, inf < 0.1%, acc < 0.1%, imp = 0
[1 sec, 12219 itr]: obj = (0.00804435), mov = 12219, inf = 3.6%, acc = 8.8%, imp = 90
[2 sec, 29248 itr]: obj = (0.00900024), mov = 29248, inf = 3.5%, acc = 6.1%, imp = 105
[3 sec, 45527 itr]: obj = (0.00933895), mov = 45527, inf = 3.6%, acc = 5.4%, imp = 120
...
[57 sec, 960654 itr]: obj = (0.0145749), mov = 960654, inf = 3.6%, acc = 3.2%, imp = 331
[58 sec, 977445 itr]: obj = (0.0146093), mov = 977445, inf = 3.6%, acc = 3.1%, imp = 333
[59 sec, 993630 itr]: obj = (0.0146159), mov = 993630, inf = 3.6%, acc = 3.1%, imp = 335
[60 sec, 1009491 itr]: obj = (0.0146402), mov = 1009491, inf = 3.6%, acc = 3.1%, imp = 337
1009491 iterations, 1009491 moves performed in 60 seconds
Feasible solution: obj = (0.0146402)
When running the GAMS model
set i /1*75/;
alias(i,j);
positive variables x(i), y(i);
x.up(i) = 1.0;
y.up(i) = 1.0;
variable z;
equation obj;
obj.. z =e= smin((i,j)$(ord(i)>ord(j)), sqr(x(i)-x(j)) + sqr(y(i)-y(j)));
model m /all/;
I get the following log:
LocalSolver 24.4.1 r50296 Released Dec 20, 2014 LEG x86 64bit/Linux
LocalSolver 5.0 (Linux64, build 20141219)
Copyright (C) 2014 Innovation 24, Aix-Marseille University, CNRS.
All rights reserved (see Terms and Conditions for details).
Searching for equations that define variables... found 0
Instance: 150 Variables
0 Constraints
19583 Expressions
41929 Operands
time | iterations | objective
0s | 0 | 0.00000000e+00
1s | 14256 | 8.25206698e-03
2s | 31361 | 9.29200900e-03
3s | 48867 | 1.00758959e-02
...
57s | 981586 | 1.42478888e-02
58s | 998156 | 1.42815908e-02
59s | 1014518 | 1.43061969e-02
time | iterations | objective
60s | 1030756 | 1.43061969e-02
Stopped due to time limit.
Feasible solution found.
Objective Value: 1.43061969e-02
Writing pow(z,2) as z*z in the LocalSolver models makes things worse:
831813 iterations, 831813 moves performed in 60 seconds
Feasible solution: obj = (0.0139557)
That is an interesting experiment. I would have expected to see some difference in the number of evaluations per second.
ReplyDelete