Currently, I am working on a project in which I am working with multiple column generation models. This makes that I need to be able to set requirements such as the generation of cuts in a flexible way, on a per model basis. Hence, I would like to adjust fields in the Configuration on a per model basis.

As far as I can tell from the current code, this is not possible. Is this correct?

Currently, it is assumed in the framework that an integral solution necessarily also leads to an integral objective function. This is for example used in determining if a node can be pruned.

Clearly, this can always be enforced by scaling of the objective coefficients, but this strategy may lead to poor performance for the LP solves in cases where the scaling factor is large. Moreover, it requires some bookkeeping of the scaling that occurs.

Clearly, a user could fix this by overriding these respective methods that use this behaviour in his implementation of the branch and price framework.

However, I would believe that this use case is so common that it would maybe be a good thing to introduce this in the framework itself, for example by using a switch that determines if this behaviour is needed.

Currently, the TSPLibTour class (tspLibReader package) which models a tsp lib tour is not very practical in use:
-Tours need to be added and accessed via the TSPLib instance
-Tours don't keep track of their length. To get the length of a tour, one needs to invoke tspLibTour.distance(tspLibInstance); which recomputes the length of the tour with respect to the given TSPLib instance.

Proposed changes:
-Separate TSPLibInstance and TSPLibTour classes, thereby making them independent:
--Move the code which reads/parses a TSPLibTour from the TSPLibInstance to the TSPLibTour class
--Add a field to TSPLibTour which stores the length of the tour
--Remove the addTour() method from TSPLibInstance; this doesn't really make much sense
Note: These changes have implications for the other classes in the tspLibReader package. This has to be checked.

Currently, reflection is used to create a new instance of a PricingProblemSolver extends AbstractPricingProblemSolver.

However, reflection may fail in case a constructor is used that uses additional parameters over those used in the default constructor. Consider for example

PricingProblemSolver extends AbstractPricingProblemSolver<T,U,V> {
   public PricingProblemSolver(T dataModel, V pricingProblem, boolean flag) {
      ...
   }

   ...
}

For this example, reflection will fail. Moreover, it is relatively difficult to track down the actual cause of this.

I would suggest to change the use of reflection here by letting the user provide a factory himself for creating new instances of the solver. The actual code needed for this would be relatively limited, especially with the use of lambda's.

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.

Column Manager

Hereby the proposed issue to discuss the design of a column manager. While the design that I have in mind is not fully complete yet, I think there are some interesting issues to discuss.

Design

The column manager should be flexible in my opinion. That should mean that the user should be able to use problem-specific knowledge if needed, but that at the same time some good base implementations should be available.

My suggestion is thus to go for an interface ColumnManager, which contains the methods

• void addColumns(List<W> columns)
• void updateColumns()points
• List<W> getCurrentColumns()

to control the current columns. Possibly, the second method could be combined with the first or third, depending on the actual implementation (see also below).

Further, we could e.g. provide the class AgingColumnManager implements ColumnManager and BasicColumnManager implements ColumnManager, which respectively use an aging strategy and simply retain all columns. (Or some similar strategies based on the most common used methods.)

Discussion points

One major point of interest is how the actual columns in the master problem are managed. Namely, a change in the chosen columns in the column manager should be reflected in the master problem. One option would be to add a removeColumn method in the Master problem.

Another major point of interest is the integration with a strong branching framework. Namely, in such methods, the RMP has to be solved multiple times. For this reason, I would propose to have the actual updating separated from the addition of columns to the master problem. However, I would say it would be good to include such considerations already now, instead of having to redesign after the implementation of strong branching.

Another point of interest is how the user chooses between different column managers. One option is to simply make the user choose one in implementing his version of the master problem. However, this makes it less easy to switch between managers. An alternative would be to pass it in the constructor of the Master problem.

There are some cases in which a parameterized class is used without any type arguments. In total, IntelliJ reports 113 warnings associated with the raw usage of parameterized classes on the development branch. While some are present in the examples, a large proportion is also present in the public API. The problem with the latter is that the user also has to use some raw types in his own code, for example in the case of listening for branching decisions. This gives some warnings that need to be suppressed in some IDE´s.

The manual misses the additional parameter boundOnMasterObjective in the constructor of ColGen that was added in release 1.1.

I only recently noticed that all package names have been switched from camelCase to lower case in the development branch. However, this means that all old code that would like to benefit from the most recent bug fixes will have to switch all package names. Moreover, when switching back for some other reason, all changes will have to be reverted again.

Would it maybe be possible to delay the switch of package names to a major version bump, such that bug fixes in the development branch can be used in old code without the need to change all package names, which is quite some work with very little benefit for the user? Maybe such a major version change can, for example, be made when adding the column manager and parallel framework, as these are changes that will require changes to the public API anyhow.

The maven build was not working. It was necessary to fix a few pom.xml configurations. There are also test failures that were not corrected, so to check the adjustments on pom.xml file it is necessary to run the maven build with the skipTests parameter.

Currently, the nodes in the Branch-and-Price tree (AbstractBranchAndPrice.java, frameworks.columnGeneration package)are solved one by one. To take advantage of modern CPUs, functionality should be added to allow these nodes to be solved in parallel. This can be realized by rewriting the method public void runBranchAndPrice(long timeLimit). Some worker threads having access to the queue containing the BAPNodes can take nodes one by one and solve them.

• Synchronization is obviously required to access the data fields in AbstractBranchAndPrice.java.
• Ideally, when a node is solved, the other worker threads are informed about the results. If for example a better integer solution is found, computations in a node may be interrupted based on the bound of the node.

Issues which have to be taken care off:
-GraphManipulator.java: for efficiency reasons, there's currently only one master problem and pricing problem. When processing a node, the master problem and pricing problem are modified automatically to reflect the problem represented by the node, i.e. the branching decisions modify the state of the master/pricing problems. Solving multiple nodes in parallel would require duplications of the master and pricing problems.
-SimpleBAPLogger.java needs to be rewritten: logging becomes more difficult. Logging messages from various nodes being solved in parallel may not become tangled up.
-bapNodeComparators: it must be guaranteed that the tree is processed in a consistent order, thereby having a deterministic solve procedure, each time an instance is solved with the exact same settings.

Create a graphical interface showing the Branch-and-Price solve procedure:
-Show the branch-and-price tree as it is being solved. This can be implemented in the same way as the SimpleBAPLogger.java class (the latter class is merely a textual interface showing the same information). It is nice if you can see the branch-and-price tree 'grow'.
-Clicking on a node should give basic information about the node
-Branching decisions should be visible
-The final solution should be exportable to some vectorized image class (e.g. pdf).
-Perhaps a window showing basic information such as best integer solution, lower bound etc

Joris,
There is potential minor glitch in the maven scripts. pom.xml in the root directory excludes /org/jorlib/frameworks/columnGeneration/tsp//*. Eclipse respects this wish, but then AllFrameworksTests.java fails to compile due to a broken import. Nota bene, IntelliJ appears to ignore the exclude line. I can't tell whether it's an Eclipse issue, an IntelliJ issue, an issue in any of the maven plugins or simply a user error. Still, it looks likely that AllFrameworksTests is to be excluded once columnGeneration/tsp was excluded.
Regards,
Gabor

Enforcing branching decisions may lead to infeasibility at nodes in the branch and price tree. Currently, this does not seem to be handled in CutGen and hence in AbstractBranchAndPrice.

I would be willing to work on this, as I need it in my own code.

In ColGen, the documentation for the method invokePricingProblems(long timeLimit) states the following:

 /**
     * Invokes the solve methods of the algorithms which solve the Pricing Problem. In addition,
     * after solving the Pricing Problems and before any new columns are added to the Master
     * Problem, this method invokes the {@link #calculateBoundOnMasterObjective(Class solver)
     * calculateBoundOnMasterObjective} method. 
     * 
     * @param timeLimit Future point in time by which the Pricing Problem must be finished
     * @return list of new columns which have to be added to the Master Problem, or an empty list if
     *         no columns could be identified
     * @throws TimeLimitExceededException TimeLimitExceededException
     */

It is currently somewhat unclear from the documentation if the columns are indeed added to the master by this method or not. This may be important, as adding columns to a model most likely makes querying information (like objective value / solve status) impossible.

Dear Joris,
I've found that sqrt() method for BigDecimals sometimes not comply its contract.
For example,
let exactSqrt be BigDecimal represented by the string
String str = "0.352818528921979802147666515426902895727765101266038472739273675725801740461899203391467404999652538893639944052164993861983322930689421050680216977023059231670566602635420201308103469059177274411042449967235640170639404861525798685782654348576008053906678123883330032297238500985193573602497626771580945594770502324168762166567267289269665176402913948019856635315861428993880073282624381118485716289019571647659739495016074896218885978289930340857274515862259731833170589692399895634244147482703269890913247408478923447178902017779845443742308844558419999046111467812933248023432427998259994182648578288775189490102071574925542172618705808377981407075661662506742408661232720032172324989308087757531861080580705851938971046656424285025030048776692043487994681169121806548569325273977674268512834848319197541770346893931298171263359209287656256258646644947830231869419567842967424731270811652666974200603722897904972781881580215186731799243387581020765695927222985513092811072096813507351486163616474354491678516423019462856092324589467805417576434369118271125610599862858091034066115393896376402586115322883185629500789989825539099146963464597667690086645833677773341477425089421202029845828438186267290619982627882863531585505515611951359679835295645460495124946561810293085634756353824263832486284294130150330118760419800451287490407783325022093281030504666007839427958453674663221723404057631681719148427415412519993998928227188905950986505087130321733361332156307945821264095564986339643413952656671077302618008809419170629325044973291573447163149540989060334863465155227701549160360633076458829101325288181727254148455952801479839414624838237422509188727938777531618602609770842427633605357541405468766390741255444162263154213109493016536875507122768177992567211419631697956177013676147279765005362827247748175113476912061656596560057107219180031161086243871513570693257886733246854019430780326947936432096164343749503593404634630874853900858530925398333908462443249715617740821018862850469001766145798985952338158907879181848149273610535411146431164860190045987407079776737665145855618269772150097545656533084155333408671462357567952863327464733354130776616979840611935007402670571489089668548000566788250160846791012993775567439582182725205696062583108329707566149812378805220075179590531688600283608991116551549027626948019331454835003314143801424170814628183200055052199722542207640173290280989264977286415610857154441019808138140819856280410105031134448183196991569236564590128053475070955652666628369465344771805924916499026673246861918192823814334395024295138823232784709065496229159508579419100068387896656615250289291758465598666278370085239497533286365488975303055116815329102108942419789159408743304837147769168826679563309806682084876882871097306440805958691670681692306549364491345283413772350464609125873897690388407474850326909999101415928102266360806164931776847358063319741306986987628745641280473524000212369792965384091797156403233777795567784543089119411659393168440334248938741623001128517522693879403929699173451781412798671665283558729628243926890969910443705973489192155576353499381779194610671587110478486168711282156757950565546363036019684717556713624143788093810345688751549193665721896867887651320967000222128167164946865556889602661431879227060777814881492519547779448310707438750917861990561928144098861424157634058497094462991766917173509132343518475084202673630176061598854141914185610767706802039701642072360625842378688027735898240182190514393189209471611768527100950310316851880853478199424580668628085693182998731100236819825441203790704941193496754099933586278887732102406442366897274992111227286780538771607254703391727435908633086669314433562019482301856480278389899972125503889024035852303562592479624352423337002906871575935923566494087298753092343486998023539344694510533797805958900582731852193990439519387549384829431113980579322708657363957164395621754828226758348067425530114629280261288667931574298350041682965467047588359489270073143306999546737192711175822029705263447027865758551542802171488905955004349464501480093234324812778987292165459441941026474022142289145222953357220372418411212413061286574450794826437795190069128780886322873705075391534786287589843850190532006721823083493988784719966839685662262264057458858102263578441838880872379410128677308321014897665822450598742323482617706556668314972948257303337118691806018319646689269303327895611192483290610412447084434138915732180208661257866451990865563784573699574180113438083551175839547069343207045045995100912147324966281922502715105823762488576030121131547913526483123729519773892343318565326104868289395276455971388735259382226159413912984029551781738507760341551002029698244452208252501876382885200201519676863857276544629621043623553022169433277290829018245988763416544714675486727259277158207185683059120469903788050023125005340124434545488528442744313808998213896416775571508334831773577301265300131926124116720552814768332474881127016239632373827247236037212368475176197284063580380941316779730166327775936730580436889438218610438044839337499052077613183040131513844261362138421340482537949355008184657331131802878928188016227607049663793923496957161690184263051610305144160357410316194354127288952746801158072255627528356254285419729629914150135164293325498786148924752199146507320087447951639563162872093511891508859874602833528357633853230657750414976922360211994756093221208726220406868776436423802282853111630343720137345935295997001814433021729906260871559252222785750795910525236903608970515342971450150471140143424730302419832493045288822449089904121958127502411554916890000523296881346660246083743133530717406880789993705668249624474982096681744820733458578119329965309671669003956057605867177163829210966938191726511853645119095575338547037668182994797666943720389432824576727544324133629219070818056301690488891414444637139445286226789026200554535161974614349396819623126119487492383584029405209572120869911038247087356343641894799034464020392552038747499914221074709047988903494270079315963932888035593068602395612879290719088991015317352105164692480211676756550307172096101637696730714405029471608453893636023178565563010040550935381304155988922549067016051209896944367217070301142516901257757847663657027699473130521129513917273661361656490890291200300878354926042615514456147252662943337364841398596952462369372282916304134920158141647180675038504459880237319";
Then the code:

BigDecimal exactSqrt = new BigDecimal(str);
BigDecimal number = exactSqrt.multiply(exactSqrt);
MathContext mathContext = new MathContext(exactSqrt.precision() + 1, RoundingMode.HALF_UP);
BigDecimal rounded = exactSqrt.round(mathContext);
BigDecimal sqrt = MathUtil.sqrt(number, mathContext);
BigDecimal difference = rounded.subtract(sqrt);
BigDecimal scaledDifference = difference.scaleByPowerOfTen(difference.scale());
System.out.println("Scaled difference: " + scaledDifference.toPlainString());

produces
Scaled difference: -465100 instead of zero.