MULTI.adoc

Solving Multiple Variants of a Problem

Introduction

If the problem we want to solve has multiple variants we have different options:

• Mixed Integer approach - adding integer variables representing the variants

• Simultaneous optimization of all sequences eliminating "bad ones" successively.

See also MINLP where this issue is discussed for single node optimization.

As example we use the time constraint variants of TandEM where the problem variants represent possible planet sequences. When we can utilize multiple cluster nodes the "simultaneous optimization" approach looks superior because it needs less communication between the nodes since each variant runs at a single node. Both approaches are implemented as examples here so you can check yourself or use the examples as blueprint for solving your own problem.

We used our small five node home cluster (4 x AMD 3950x + 1 x AMD 2990WX) to execute the example code.

The Simultaneous Optimization Approach

See raytandem.py First we search for the optimal planet sequence using all cluster nodes eliminating "bad ones" successively. Each sequence is optimized on a single node to minimize communication between the nodes. Only the current value of each sequence needs to be transferred to sort the variants and eliminate the bad ones.

...
def test_multiretry(num_retries = min(256, 8*mp.cpu_count()),
             keep = 0.7, optimizer = de2_cma(1500), logger = logger(), repeat = 10):
    seqs = Tandem(0).seqs
    n = len(seqs)
    problems = [Tandem(i) for i in range(n)]
    ids = [str(seqs[i]) for i in range(n)]
    t0 = time.perf_counter()
    for _ in range(repeat):
        # check all variants
        problem_stats = multiretry.minimize(problems, ids, num_retries, keep, optimizer, logger)
        ps = problem_stats[0]
...

Output:

iteration 1
problem Tandem 8 [3, 2, 3, 5, 6] -179.9965989142086 time = 17.04
...
iteration 2
problem Tandem 6 [3, 2, 3, 3, 6] -633.9727140539997 time = 42.15
...
iteration 3
problem Tandem 6 [3, 2, 3, 3, 6] -889.8883866408449 time = 67.01
...
iteration 4
problem Tandem 6 [3, 2, 3, 3, 6] -889.8883866408449 time = 87.17
...
iteration 5
problem Tandem 6 [3, 2, 3, 3, 6] -1201.8411107184736 time = 109.43
...
iteration 6
problem Tandem 6 [3, 2, 3, 3, 6] -1340.11636813011 time = 127.15
...
iteration 7
problem Tandem 6 [3, 2, 3, 3, 6] -1340.11636813011 time = 139.96
...
iteration 8
problem Tandem 6 [3, 2, 3, 3, 6] -1350.9703853576225 time = 152.41

After we found the best variant - which is stored at problem_stats[0] - after about 152 sec we have two options:

Either we use the intermediate result and improve it further using only a single node, since transferring the intermediary result to all nodes would be difficult and expensive:

    for _ in range(10):
        # improve the best variant using only one node
        fval = ray.get(ps.retry.remote(optimizer))
        logger.info("improve best variant " + ray.get(ps.name.remote())
                    + ' ' + str(ray.get(ps.id.remote()))
                    + ' ' + str(ray.get(ps.value.remote()))
                    + ' time = ' + str(dtime(t0)))
        if fval < -1490:
            break

Or we start from scratch and use all nodes,

    # optimize best variant starting from scratch using all nodes
    logger.info("improve best variant " + ray.get(ps.name.remote())
                + ' ' + str(ray.get(ps.id.remote()))
                + ' ' + str(ray.get(ps.value.remote()))
                + ' time = ' + str(dtime(t0)))
    problem = problems[ray.get(ps.index.remote())]
    _rayoptimizer(optimizer, problem, 1, max_time = 1200, log = logger)

Output:

31.9 0 0 0 -1145.653009 -10.04 6 1 [-1073.55, ...] [7964.49897483047, ..., -1.617119714389485]
...
78.69 0 0 0 -1401.879901 -10.04 9 1 [-1391.59, ...] [7965.609591511901, ..., -1.93367579787295]
...
200.23 0 0 0 -1500.163712 -5.44 10 1 [-1415.92, ...] [7989.400476995166, ...,-2.0355620874569107]

After 150 + 200 = 350 sec we found a nearly optimal solution.

The Mixed Integer Approach

The alternative MINLP approach is implemented by using the MINLP variant of the problem Tandem_minlp() which adds additional decision variables for all intermediary planets. Then we simply apply fcmaesray.rayretry.minimize performing the optimization using all nodes. See tandem_minlp.py

...
def test_tandem_minlp(opt, num, max_time = 1200, log = logger()):
    problem = Tandem_minlp()
    minimizers = None # remote actors created by minimize will be reused
    log.info(problem.name + ' ' + opt.name)
    for i in range(num):
        ret, minimizers = minimize(problem.fun, problem.bounds, max_nodes, None, num_retries = 20000,
            value_limit = 12.0, logger = log, optimizer=opt, max_time=max_time, minimizers=minimizers)
        print("solution: ", i+1, ret.fun, str(ret.x))
    for minimizer in minimizers:
        ray.get(minimizer.terminate.remote())

Output:

61.83 0 0 0 -818.979097 -20.32 7 1 [-808.45, ...] [8622.194085263913, ..., 2.6511251436901038]
...
131.41 0 0 0 -958.608335 -20.32 7 1 [-955.86, ...] [8990.730191806304, ..., 2.8448686335455924]
...
262.47 0 0 0 -1339.345015 -20.32 8 1 [-1256.89, ...] [8441.597725830494, ..., 3.4110498702115333]
...
666.97 0 0 0 -1339.903135 -20.32 8 1 [-1339.88, ...] [8441.693210408625, ..., 2.9675702690199963]
...
1185.33 0 0 0 -1364.020134 -20.32 9 1 [-1364.02, ...] [6121.633413068753, ..., 3.4893091411594392]

Even after 1200 sec (much more time as for the simultaneous optimization approach) we are still stuck at -1364. As expected the mixed integer approach is inferior when we can utilize multiple cluster nodes.