MultiSolve Introduction

Hello world

This section introduces the multi solve library via a Hello World example. In this example five Transportation problems are solved, whereby up to 2 solves are executed in parallel. The difference between two of these transportation problems is the amount of supply and demand. Note that the amount of supply and demand is in balance for each of the data instances.

The multi solve library contains only one procedure: multiSolve::pr_multiSolve. A call to this procedure may look as follows :

 1Procedure pr_test2X2TransportProblem5TimesGenerate {
 2    Body: {
 3        ! Prep the GMP.
 4        rslva_ut::t001_su::pr_setupSolved();
 5
 6        ! Perform test
 7        multiSolve::pr_multiSolve(
 8            ep_baseGMP                    :  '', ! Using callbacks with 'Generate' semantics.
 9            ep_onNextSessionInstance      :  'rslva_ut::t001::pr_onNextSessionInstanceGenerate1',
10            ep_onSessionInstanceCompleted :  'rslva_ut::t001::pr_onSessionInstanceCompletedGenerate1',
11            p_maxParallelGMPs             :  2,
12            p_maxThreadsPerSolve          :  1,
13            p_startingSolutionMethod      :  1);
14
15        aimmsunit::AssertTrue(
16            descr :  "multiSolve::pr_multiSolve(): Small working run",
17            expr  :  aimmsunit::CompareEqual(t001_su::p_obj,t001_su::p_objVerified),
18            cont  :  1);
19    }
20    aimmsunit::TestSuite: resolveAsync;
21}

Remarks about the above code fragment:

  • Line 4: Ensure data is available, etc. Not detailed here.

  • Lines 7-13: The entire call to the pr_multiSolve.

    • line 8: By not specifying a base GMP, the responsibility to generate an entire GMP is put to the callback procedures. This is referred to in the remainder of this document as: the callback mode is 'generate'. The alternative callback mode is 'modify', whereby the callback procedures are responsible for updating the LP matrix as needed. In practice, the easier callback mode for the application developer is the callback mode 'generate'; as in this mode the AIMMS Matrix Generator will ensure a GMP is generated consistent with the data in the model identifiers.

      Tip

      From a software engineering point of view, it makes sense to start with the callback mode 'generate'; this mode permits the model builder to focus on adding code to update the model identifiers only. If it turns out that relatively significant time is spent in the generation of GMP’s, the alternative callback mode 'modify' can be considered.

    • line 9 and 10: The names of the callback procedures; please make sure their signatures match multiSolve::pr_onNextResolveSessionInstanceSignature and multiSolve::pr_onResolveSessionInstanceCompletedSignature respectively. Examples of such callback procedures are presented below.

    • line 11: p_maxParallelGMPs: Up to this number of solves can be executed in parallel.

    • line 12: p_maxThreadsPerSolve: The maximum number of threads available to a single solve. Please ensure that p_maxThreadsPerSolve X p_maxThreadsPerSolve <= the number of cores on your computer.

    • line 13: p_startingSolutionMethod A good starting solution can significantly speed up the solution process. The value 1 for the callback method 'generate', indicates to use the values of the model variables.

  • Line 15-18,20: This example text is taken from the unit tests that come with the multi solve library.

Clearly, the model builder needs to provide proper callback procedures; one to generate (or modify) a GMP, and another one to handle the results. Next, we discuss an example callback procedure to generate a GMP.

 1Procedure pr_onNextSessionInstanceGenerate1 {
 2    Arguments: (ep_gmp,ep_handle);
 3    Body: {
 4        t001_su::p_iter += 1 ;
 5        if t001_su::p_iter > t001_su::p_maxNoInstances then
 6            ep_handle := '' ;
 7            p_procedureReturnCode := 0 ;
 8        else
 9            ep_handle := element( t001_su::s_instances, t001_su::p_iter );
10
11            ! Update model parameters for this variation.
12            t001_su::p_supply(t001_su::i_src)  += 1 ;
13            t001_su::p_demand(t001_su::i_trgt) += 1 ;
14
15            ! Create a new GMP, ensure that its name is unique.
16            ep_gmp := gmp::Instance::Generate( t001_su::mp_transport,
17                    formatString("Instance %s of t001_su::mp_transport", ep_handle ) );
18
19            p_procedureReturnCode := 1;
20        endif ;
21        return p_procedureReturnCode ;
22    }
23    DeclarationSection Argument_declarations {
24        ElementParameter ep_gmp {
25            Range: AllGeneratedMathematicalPrograms;
26            Property: InOut;
27        }
28        ElementParameter ep_handle {
29            Range: Integers;
30            Property: Output;
31        }
32    }
33    DeclarationSection Local_declarations {
34        Parameter p_procedureReturnCode;
35    }
36}

Remarks:

  • Lines 5-8: First it is checked whether there is any work left to be started. If not, return 0; which is interpreted by the library that no more solves are needed.

  • Lines 11-13: Update the model sets and parameters as needed.

  • Lines 15-17: Create a GMP using GMP::Instance::Generate(). Make sure the name of the GMP generated is unique within your application.

Just as there is a callback to specify the GMP to be solved, there is a callback to retrieve the results. An example is given below.

 1Procedure pr_onSessionInstanceCompletedGenerate1 {
 2    Arguments: (ep_gmp,ep_finishedSolverSession,ep_handle,ep_step);
 3    Body: {
 4        ! Translate the handle to index values meaningful for the business.
 5        ep_inst := ep_handle ;
 6
 7        multiSolve::pr_storeSolutionInModelVariables(ep_finishedSolverSession);
 8
 9        ! Retrieve solution, here only the objective value.
10        t001_su::p_obj(ep_inst) := t001_su::v_obj ;
11
12        ! After this solve, no further solve steps are needed to solve for the data instance at hand.
13        return 0 ;
14    }
15    DeclarationSection Argument_declarations {
16        ElementParameter ep_gmp {
17            Range: AllGeneratedMathematicalPrograms;
18            Property: InOut;
19        }
20        ElementParameter ep_finishedSolverSession {
21            Range: AllSolverSessions;
22            Property: Input;
23        }
24        ElementParameter ep_handle {
25            Range: Integers;
26            Property: Input;
27        }
28        ElementParameter ep_step {
29            Range: Integers;
30            Property: Input;
31        }
32    }
33    DeclarationSection Local_declarations {
34        ElementParameter ep_inst {
35            Range: t001_su::s_instances;
36        }
37    }
38}

Remarks:

  • Line 7: Retrieve the solution from the solver session and store that solution in the model variables.

  • Line 10: Of the results retrieved, only the objective value is stored in this example.

  • Line 13: Return 0; this indicates that for this instance, no further solve steps are needed.

This ends the hello world example for the multi solve library. We continue with detailing the library.

Callback modes

This library supports two modes, called callback modes:

  • modify

    In this mode, the callback procedures are responsible for modifying the coefficients of a GMP as needed. This mode is tuned towards efficiency; costly matrix generation steps are avoided, and there is choice in starting points for efficient execution.

  • generate

    In this mode, the callback procedures are responsible for creating a new GMP for every solve. This mode is tuned towards modeling efficiency;

The solve steps for an Operations Research problem

Many Operations Research (OR) problems are solved by solving a single Mathematical Program (MP). However, for some OR problems, it is needed that multiple Mathematical Programs are solved. Solving a single MP is then called a solve step. A typical example is to first solve a given problem to feasibility, and then to optimality. This library uses solve steps, or just steps, to cater for multi step OR problems.

As an aside, there are also OR problems that do not require an MP to be solved. This library is of no use for such OR problems, and therefore these OR problems are not considered here.

Consider the following overview of multiple data instances, whereby handling a data instance requires a sequence of multiple solve steps.

../_images/multi-var-multi-step.png

Remarks:

  • As there is a dependency between Var 1, step 1 and Var 1, step 2, they cannot be solved in parallel.

  • As there is no dependency between Var 1, step 1 and Var 2, step 1, they can be solved in parallel.

References:

  1. Implementing Advanced Algorithms for Mathematical Programs

  2. The GMP Library

  3. The AIMMS Unittest library

Alternatives

  1. Stochastic programming

  2. Robust optimization

  3. Monte carlo: