Lessons Learned - User-Level Workflow Design: A Bioinformatics Perspective - page 155

Gradual Increase of the Search Depth

From a theoretical point of view, there are in the first place only two distinct
sets of synthesis solutions that are interesting to consider:

1. the/one shortest solution,
2. all solutions.

Searching only for one shortest solution (typically simply the first that is
encountered), however, is usually not sucient in practice, as most applica-
tions comprise several adequate workflow variants, and not necessarily is a
shortest solution the actually intended one. Thus it is reasonable to leave the
selection of one particular solution to the user. However, finding all solutions
is in practice usually not possible, as only very few synthesis universes can
be explored completely (cf. Section 7.1.1).
Consequently, it is in practice reasonable to define an upper bound for the
length of the considered solutions and start synthesizing with a small search
depth, proceeding to greater depths only when it is clear that the solutions
found in smaller ones are not sucient. This strategy has also been applied in
the detailedly described solution refinement strategy of the EMBOSS work-
flow scenario (cf. Section 3.3.4): In the unconstrained case, the default limit
of 1,000,000 solutions (as defined by PROPHETS) has been reached while
the synthesis algorithm was still exploring solutions of length 4. Taking this
depth as the preliminary upper bound for the search, constraints were added
until the synthesis algorithm only returned a manageable set of about 30 so-
lutions. Only then, depth 5 of the synthesis universe was taken into account
and explored for further admissible solutions.
As detailed in Section 7.1.2, the runtime performance of the synthesis can
be roughly estimated as exponential, or O ( m d ), where m is the number of
services in the domain model and d the considered search depth. When trying
to synthesize longer workflows based on more complex domain models, state
explosion is likely to strike sooner or later and hamper the workflow design
process. For this case, there is a simple but effective, divide-and-conquer-style
workaround: perform two (or more) short syntheses instead of one long one,
since ( m d 1+ d 2 ). Typically, for longer workflows particular

steps or services that are to be included can be identified beforehand, sim-
ilar to looking out for suitable stones to step on when planning to cross a
wild river. Instead of adding constraints that enforce their inclusion, these
points can then be used to split a large synthesis problem into smaller, faster
synthesizable ones.

( m d 1 + m d 2 ) O ≤O

Incremental Specification of Constraints

Instead of requiring to specify all characteristics of the intended applica-
tion from the beginning, loose programming enables and encourages the user