Managing the bisection and ordering

The second problem is solved in the following way: assume that at some step of the algorithm the bisection process leads to the creation of $k$ ${\cal W}$ such that $N+k-2>M$. As we have previously considered the $i-1$ elements of ${\cal I}$ we may use them as storage space. This means that we will store ${\cal I}_j, j\ge i$ at ${\cal I}_{j-i+1}$ thereby freeing $i-1$ elements. In that case the procedure will fail only if $N+k-i+1>M$.

Now we have to manage the ordering of the ${\cal W}$. We have defined two types of order for a given set of boxes ${\cal I}$:

1. maximum equation ordering: the box are ordered along the value of $C={\rm Max}(\vert\overline{F_k({\cal I})}\vert, \vert\underline{F_k({\cal I})}\vert)$ for all $k$ in [1,$n$]. The first box will have the lowest $C$.
2. maximum middle-point equation ordering: let $C_i$ be the vector whose components are the middle points of the intervals ${\cal I}$. The box are ordered along the value of $C={\rm Max}(\vert\overline{F_k(C_i)}\vert, \vert\underline{F_k(C_i)}\vert)$ for all $k$ in [1,$n$]. The first box will have the lowest $C$.

When adding the ${\cal W}$ we will substitute the ${\cal I}_i$ by the ${\cal W}$ having the lowest $C$ while the others ${\cal W}$ will be added to the list ${\cal I}$ by increasing order of $C$. The purpose of these ordering is to try to consider first the box having the highest probability of containing a solution. This ordering may have an importance in the determination of the solution intervals (see for example section 2.3.5.2).

This method of managing the bisection is called the Direct Storage mode and is the default mode in ALIAS. But there is another mode, called the Reverse Storage mode. In this mode we still substitute the ${\cal I}_i$ by the ${\cal W}$ having the lowest $C$ but instead of adding the remaining $n$ ${\cal W}$ at the end of the list ${\cal I}$ we shift by $n$ the boxes in the list, thereby freeing the storage of ${\cal I}_{i+1},\ldots, {\cal I}_{i+1+n}$ which is used to store the remaining $n$ ${\cal W}$. In other words we may consider the solving procedure as finding a leaves in a tree which are solutions of the problem: in the Direct Storage mode we may jump during the bisection from one branch of the tree to another while in the Reverse storage mode we examine all the leaves issued from a branch of the tree before examining the other branches of the tree. If we are looking for all the solutions the storage mode has no influence on the total number of boxes that will be examined. But the Reverse Storage mode may have two advantages:

• if we are looking for only one solution it may enable to find it more rapidly (but that is not compulsory, see section 2.3.5.4),
• as we are following one branch at a time we will consider very rapidly small box that either will lead to a solution or will be discarded thereby enabling to free some storage space. Hence the storage space available in the reverse mode will be in general higher than in the direct mode: a practical consequence is that a problem may not be solved with the direct mode due to problem in the storage while with the same amount of storage solutions will be obtained in the reverse mode.

To switch the storage mode see section 2.3.4.5 .We may also define a mixed strategy which is staring in the direct mode and then switching to the reverse mode when the storage becomes a problem (see section 8.3).