There are currently two methods for solving the mapping problem in ArchEx: monolithic optimization (“eager”) and iterative (“lazy”) optimization. When creating a problem instance, one of them is selected by default (user can modify this in the code of the problem class). To select a solution strategy after the problem instance is created, type:

prob.setAlgorithm(<alg>)

where <alg> is either “eager” or “lazy”.

##Monolithic (“eager”)

The eager optimization method solves a monolithic problem, which includes all the optimization constraints. Since some of them may originate from approximations (e.g., reliability constraints), optimality is only guaranteed within the error bound due to the approximation.

Certain constraints (e.g., reliability) may require creating auxiliary data structures and variables in order to be correctly encoded. This may take some time and it is only done if the problem instance is created with eager optimization selected as a default solution strategy or if the user changes the strategy to eager by using prob.setAlgorithm() command. ArchEx will notify the user that aux data structures and variables are created by a console message.

Under the hood, when the problem is created, ProcessConstraints() method reads the patterns from the problem description file using the ConstraintHandler class. MILP formulations of constraints of different classes (e.g., timing, interconnection) are then fetched from it to the problem class and divided into two groups: constraints and auxiliary constraints. The latter included constraints that are used in the monolithic optimization, but not used in iterative. Basically, when eager approach is selected, before solving the problem these two groups are combined into one, which gives a set of all available constraints.

##Iterative (“lazy”)

NOTE: currently supported only for EPN problems.

Alternatively, the lazy method leverages a coordination of specialized solvers. In this paradigm, the MILP solver is called iteratively on smaller problem instances including only a subset of constraints (e.g., interconnection constraints) to generate candidate configurations. The validity of these configurations is then checked against the other constraints via exact analysis methods. If these constraints are violated, a conflict-driven learning function is called between iterations of the MILP solver to incrementally add new constraints to the original formulation based on the analysis of previous outcomes, prune the search space, and rapidly progress towards a feasible solution. Solving a small number of simpler problem instances can significantly reduce the execution time with respect to a monolithic approach. However, global optimality is no longer guaranteed.

In the lazy approach iterations of the MILP solver are typically much faster than eager (few seconds for each iteration for EPN problems). They alternate with the calls to the LearnCons() function, which analyses the results of the last iteration and proposes (learns) new constraints to guide the MILP solver towards a better solution.

To have more understanding on how the lazy approach works, you can run EPN demo problems. They are solved iteratively (for the sake of a live demo), because solving a monolithic problem takes several hours.