Interaction between AbstractMaster and Master may lead to subtle bugs

[rowtricker]

Currently, the implementation is such that the Master class (or in general the class extending AbstractMaster) uses super(...) to call the AbstractMaster constructor, which in turn calls buildModel(). However, this may lead to very subtle bugs in cases where fields are used that are also used in the buildModel() class. Consider a Master model with contents:

private List<IloRange> constraints = new ArrayList<>();

public Master(Data dataModel, PricingProblem pricingProblem,
                  OptimizationSense optimizationSenseMaster){
   super(dataModel, pricingProblem, optimizationSenseMaster);
}

public MasterData buildModel() {
     ...
     IloRange range = ...
     constraints.add(range);
}

This code will throw a rather unexpected NPE at the addition to the list, as the call in the super constructor to buildModel() precedes the construction of the ArrayList. Moreover, this behaviour breaks the convention to call overridable methods in constructors (see e.g. Effective Java 2nd Edition, Item 17).

It would be good if this behaviour would at least be documented somewhere. Otherwise, there should also be multiple ways out to get rid of the behaviour altogether, by for example deferring the construction of the container class AbstractMaster to the ColGen class or by moving the responsibility for building the Master problem to the user.

[jkinable]

I looked into the issue you raised and I think you've a valid point. The easiest way to fix this is to specify in the documentation that the constructor of the master class will invoke the buildModel() function.
Effective Java 2nd Edition, Item 17 indeed mentions that "Constructors must not invoke overridable methods". It would be possible to remove the call to buildModel() from the constructor, but this would hurt the 'flow' of the implementation. Suddenly users would have to remember which functions to invoke in which order, i.e. they would have to invoke buildModel() themselves. Currently, all you have to do is implement each method without worrying about the implementation. Any thoughts on this?
Either way, your comments are very helpful. If you find more issues, please let us know. In addition, I'm curious to know what your thoughts are about the library, what's missing, and what you are using it for. This helps us steer any future developments.

[rowtricker]

Thank you for looking into the issue. I would personally say that the least destructive way would be to move the building of the master object to the actual algorithm (ColGen or AbstractBranchAndPrice). This, as it provides a more durable solution, where users can't miss the note in the Javadoc or are unable to link the error they obtain to the note in the Javadoc. However, the only disadvantage here is that AbstractBranchAndPrice internally uses ColGen, meaning that ColGen should know if the master has already been instantiated. This could be solved by for example adding a new (package private) constructor that determines if the master problem should still be built. This way, a new version of Jorlib would provide a drop-in replacement of the original version, while the problem is mitigated. Moreover, one could also identify other advantages of moving the building to the implementation classes:

• It becomes easier to take the building of the model into account for the time limit through options specified in the configuration
• It allows the algorithm to decide itself when it would be most useful to build the model, for example allowing some preprocessing to occur first

However, clearly, this option would require somewhat more changes than the addition to the Javadoc. And I am not sure if this would lead to other unwanted side-effects?

[rowtricker]

I am using the library for column generation and branch and price procedures by the way (for example to solve a train unit shunting problem), but I haven't used any of the other functionality so far. What I like regarding the column generation framework is that it provides a basic framework, that allows to structure the classes needed to implement such involved algorithms. What would probably be nice for further additions to the column generation framework would be to allow the user more freedom in implementing more advanced strategies. For example regarding the use of columns in column generation (which pool of columns is currently in use, should a certain column be deleted if the current pool of columns becomes too large). The same goes for more advanced branching strategies (e.g. strong branching) and control of the branch and price tree (depth-first, breadth-first). However, these are quite clearly more advanced features.

[jkinable]

Thanks! Wrt the technical stuff: I'll get back to that later, it's a bit too busy at work at the moment.
Wrt your other suggestions:
-Controlling the branch-and-price tree: that's already possible :). See "Branch-and-Price node ordering" in the manual.
-Strong branching is something that I indeed have in mind, but that's a bit tricky to implement. Especially since I'm also planning to make BAP fully distributed (multi-threaded).
-Column pool manager: this shouldn't be too hard. Need to think about the design though since some details are rather solver specific. E.g. you may want to remove columns which have not been part of a basis for X iterations. Determining whether a column is in the basis is solver dependent. Nevertheless, I think that building some generic pool manager should be doable.