Strategies

Box Properties

(In release 2.7)

The box (IntervalVector class) is the central concept in Ibex and often this structure is too simple and required to be extended.

Consider for example a search tree, such as the one performed by ibexsolve. Assume you have several contractors involved in this search that need to calculate at some point the image of the current box by a function f. Imagine also that this function has quite a long expression so that calculating an image takes significant time:

// A contractor
class MyCtc : public Ctc {
public:
  void contract(IntervalVector& box) {
    Interval y = f.eval(box); // this line is assumed to be expensive
    // ...
  }
};

Note: For simplicity, we assume from now on that f is a fixed object that has been declared somewhere in the context (it could also be given in argument of all objects).

Recalculating this image each time a contractor is called represents a waste of time if the box hasn’t changed meanwhile. One would like to store this information in the box. This is the kind of things ‘’box properties’’ allow to do.

All is based on the Bxp interface. This Bxp interface allows to extend the simple IntervalVector data structure and to make this extension being propagated through a strategy (search tree). The extended box is then visible by all operators involved in the strategy (contractors, bisectors, cell buffers, etc.).

Note that the name of this interface is a trigram (like Ctc or Bsc) just to encourage programers to prefix subclasses by Bxp (this is a recommended usage). A box property, such as the image of the box by a given function, has to be a subclass of Bxp so let us name it BxpImage:

class BxpImage : public Bxp {
public:
  // to be completed...

  Interval image;
};

Of course, this class contains a field named image that will store the information. We could also add whatever data needed.

Constructor

It is natural to ask the constructor of BxpImage to take a box in argument and to set the image field appropriately.

The constructor of the mother class Bxp also requires an identifying number. Here is why. A box property is actually a set of instances of the Bxp interface: if the solver handles 1000 boxes at a given time, every box has it own image, hence its specific instance of BxpImage. These 1000 instances represent the same ‘’property’’ and since there may be other properties attached to the boxes at the same time, we can retreive a given property thanks to its id field. (Note: using the class name directly as identifier would be too restrictive as there may be different BxpImage properties attached to different functions f). You can simply fix this identifier to any random long number or use the next_id() function of Ibex as follows:

class BxpImage : public Bxp {
public:
  BxpImage(const IntervalVector& box) :
    Bxp(id), image(f.eval(box)) { }

  // to be completed...

  Interval image;
  static const long id;
};

const long BxpImage::id = next_id();

Note: In the case of several BxpImage properties (one for each function f) you can store identifying numbers in a map structure (see examples in the Ibex code).

To avoid confusion, we call for now “property value” an instance of the same property. So, BxpImage is a property (or a set of properties, one for each f) and the instances of BxpImage are property values.

Property update

The next step is to specify how property values are updated when the box is modified. This amounts to implement an update(...) function as follows. This function will be called at different points of the stragegy, through the trust chain principle to be explained further.

  void update(const BoxEvent& event, const BoxProperties& prop) {
    image = f.eval(event.box);
  }

Note that a smarter implementation is often desired. This is however not enough. You also have to state how the property is transformed when the box is copied (copies occur in a search each time a box is bisected or, e.g., to perform some temporary computations). This is done by implementing the copy() function:

  Bxp* copy(const IntervalVector& box, const BoxProperties& prop) const {
    return new BxpImage(*this); // implicit copy constructor is fine
  }

Using properties

Now, let us modify the implementation of our contractor. To take benefit of properties, two steps are required. First, we have to override the add_property function of the Ctc interface. This function is called by all strategies at initialization. This function takes as argument the initial box (of the search) and a container for property values: an instance of BoxProperties. This object basically just stores pointers to Bxp*, except that it can handle inter-dependencies.

Second, we have to override a variant of the contract function, which takes in argument not only the box, but also a ContractContext object which contains, among other things, the current property values container (again, an instance of BoxProperties). The BoxProperties class works like a simple map: by using the bracket operator [...] with the property id inside the brackets, you get the corresponding property value associated to the box:

class MyCtc : public Ctc {
public:

  /* Add the required property inside the map.
   * (This function is automatically called by the search). */
  void add_property(IntervalVector& box, BoxProperties& prop) {
    // if the property is not already in the list
    // (which is possible since another operator requiring it may
    // have already added it)
    if (!prop[BxpImage::id])
      // create an initial property value, and add it
      prop.add(new BxpImage(box));
  }

  /* Contract a box with associated properties. */
  void contract(IntervalVector& box, ContractContext& context) {
    // Get the desired property from the map, by its id
    // (a cast is necessary because all properties are typed Bxp*)
    BxpImage* bxp=(BxpImage*) context.prop[BxpImage::id];

    if (bxp==NULL) {
      // This happens if the property is not present.
      // It is much more safe to handle this case
      // ...
    } else {
      // Obtain directly the image (without recalculating it)
      Interval y=bxp->image;
      // .....
    }
  }
};

Lazy update

So far, we have centralized in a unique place the result of the image computation which is already good but not optimal at all. Worse, the running time of our program will likely be longer than without introducing this property! Indeed, the update function will be called basically whenever an operator change the box, which means that the funtion f will be evaluated again and again!

This event-oriented design of a property can be sometimes interesting but, clearly, it does not fit well here.

What we actually want is the function to postpone the evaluation at the latest time, that is, when someone requires it. This is called laziness. This principle can be simply applied here as follows:

class BxpImage : public Bxp {
public:
  // The class contains 2 new fields:
  // box: a reference to the box needs to be stored
  // to perform the evaluation at any time.
  // up2date: memorize whether the image is up to date.
  BxpImage(const IntervalVector& box) : Bxp(id), box(box), up2date(false) { }

  void update(const BoxEvent& event, const BoxProperties& prop) {
    // do nothing for the moment!
    up2date=false;
  }

  Bxp* copy(const IntervalVector& box, const BoxProperties& prop) const {
    return new BxpImage(box,image,up2date);
  }

  // Return the image of f.
  const Interval& get() {
    if (!up2date) {
      image = f.eval(box);
      up2date=true;
    }
    return image;
  }

  static const long id;

protected:
  BxpImage(const IntervalVector& box, const Interval& image, bool up2date) :
    Bxp(id), box(box), image(image), up2date(up2date) { }

  const IntervalVector& box;
  Interval image;
  bool up2date;
};

It is easy to adapt this code so that an update is performed only when the box modification is significant (e.g., when a contraction removes more than 1% of a component width).

Dependencies

It may happen that a property is based on another one. Imagine that you want to create a property that stores the width of the function image (of course, this example is caricatural as the width is not something you really need to store). You can extend the BxpImage class but you can also create a separate property, say BxpImageWidth.

The BxpImageWidth need to “see” the BxpImage property in the update_xxx(...) function. This is why there is also a BoxProperties map in the argument of these functions. Furthermore, we must be sure that the BxpImage is updated before BxpImageWidth. To this end, we simply have to add the identifier of BxpImage in the dependencies of BxpImageWidth. This must be done in the constructor of BxpImageWidth as shown in the following code.

class BxpImageWidth : public Bxp {
public:
  BxpImageWidth(const IntervalVector& box) : Bxp(id), w(box.max_diam()) {
  // dependencies is a field inherited from Bxp
    dependencies.push_back(BxpImage::id);
  }

  void update(const BoxEvent& event, const BoxProperties& prop) {
    BxpImage* bxp=(BxpImage*) prop[BxpImage::id];

    if (bxp==NULL) {
      // This happens if the property is not present.
      // It is much more safe to handle this case
      // ...
    } else {
     // note: we lose laziness here
      w=bxp->get().diam();
    }
  }

  double w; // the width
  static const long id;
};

For the sake of concision, we haven’t used laziness in this code. A lazy variant is necessary here.

Trust chain principle

The trust chain principle is the following:

  • Property values are always up-to-date when given to argument of a function.

Consider a function that handles properties (e.g., an implementation of the contract variant with BoxProperties, as above). It the box is modified at several points in the code, it is not necessary to perform updates as long as properties are not used elsewhere. The update can be postponed to the point where property values are transmitted to another function or, on last resort, before returning.

Note that updating all property values can be simply done via the update function of BoxProperties (this also allows to respect dependencies).

As a consequence, if the function does not modify itself the box (would it calls other functions that potentially modify it), it does not have to perform at all any update of property values.

Bisectors

A bisector is an operator that takes a box \([x]\) as input and returns two sub-boxes \(([x]^{(1)},[x]^{(2)})\) that form a partition of \([x]\), that is, \([x]=[x]^{(1)}\cup[x]^{(2)}\). This partition is obtained by selecting one component \([x_i]\) and splitting this interval at some point.

Each bisector implements a specific strategy for chosing the component. The bisection point in the interval is defined as a ratio of the interval width, e.g., a ratio of 0.5 corresponds to the midpoint.

Bisecting each component in turn

(to be completed)

Bisecting the largest component

(to be completed)

Setting different precision for variables

In real-world applications, variables often correspond to physical quantities with different units. The order of magnitude greatly varies with the unit. For example, consider Coulomb’s law:

\[F=k_e\frac{q_1q_2}{r^2}\]

applied to two charges \(q_1\) and \(q_2\) or ~1e-6 coulomb, with a distance \(r\) of ~1e-2 meter. With Coulomb’s contant ~ 1e10, the resulting force will be in the order of 1e2 Newton.

If one introduces Coulomb’s equation in a solver, using a bisector that handles variables uniformly, i.e., that uses the same precision value for all of them, is certainly not adequate.

Each bisector can be given a vector of different precisions (one for each variable) instead of a unique value. We just have to give a Vector in argument in place of a double. For instance, with the round-robin bisector:

    double _prec[]={1e-8,1e-8,1e-4,1};

    Vector prec(4,_prec);

    RoundRobin rr(prec);

Respecting proportions of a box

If you want to use a relative precision that respects the proportion betweeen the interval widths of an “initial” box, you can simply initialize the vector of precision like this:

Vector prec=1e-07*box.diam(); // box is the initial domain

The Smear Function

(to be completed)

Smear function with maximum impact

(to be completed)

Smear function with maximal sum of impacts

(to be completed)

Smear function with maximal normalized impact

(to be completed)

Smear function with maximal sum of normalized impacts

(to be completed)

maximal sum of impacts

Cell buffers

(to be completed)

Cell Stack

(to be completed)

Cell Heap

(to be completed)