Implementation Column Manager

[rowtricker]

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.

[rowtricker]

@jkinable Any thoughts on this?

[jkinable]

Sorry for the delay, I've been swamped by work over the last few weeks.
I'll go over it before the weekend.

Joris

On Thu, Oct 20, 2016 at 5:00 AM, Rowan Hoogervorst <[email protected]

wrote:

@jkinable https://github.com/jkinable Any thoughts on this?

—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
#18 (comment), or mute
the thread
https://github.com/notifications/unsubscribe-auth/ACnYyqhDUwyA7cSoRaxKsdOhEvQgZPDUks5q1y2vgaJpZM4KRMFj
.

[rowtricker]

No problem, it was just that I wanted to remind you of the issue. A small further idea that I thought of regarding a column manager is that we might also want to have a way to quickly price columns that have been previously deleted from the model.

[jkinable]

Alright, finally got a chance to look at this in detail. I'm on the job market, facing a ton of publication deadlines, chairing a conference session and I'm lacking behind with both code and paper reviews... Nevertheless I apologize for the delay :(.

I like your proposal!

• I suggest to have a default column manager. Add a method setColumnManager which enables users to supply their own column manager implementation
• A common implementation for the Aging ColumnManager is to count how long a column hasn't been in the basis of a solution. Columns which haven't been in the basis for X number of iterations, are moved to a separate column pool and removed from the master. Before invoking the pricing problem, the column pool is queried to check whether columns need to be returned to the master. Consequently, it's probably not a bad idea to let the ColumnManager implement PricingProblem (ColumnManager should be queried before any of the other more expensive pricing problems).

Wrt to the discussion points:

1. removeColumn seems indeed the most appropriate solution
2. I don't see your point? How is the strong branching behavior different from solving a normal node? The only difference is that in strong branching, only a few iterations per 'candidate' node are made, after which the best candidate is selected for further exploration.
3. I would use a default column manager, and use a setter (setColumnManager) to swap one column manager for another. My guess is that most users don't want to bother with this: they simply want 'the best' column manager.
4. Make sure the ColumnManager can be disabled, for example by providing a PassThrough column manager which basically does nothing.

Something else that should preferably be taken into account is the following. Currently, most of the BranchAndPrice (BaP) implementation is single-threaded. I would like to change this in the future to a distributed implementation as follows.
Currently there is 1 queue of unexplorerd BaP nodes. The nodes in this queue get processed one by one. I would like to add the concept of Workers. Each worker maintains its own queue of unexplorered Bap nodes. Whenever one of the workers has an empty queue, it can steal work from one of the other workers. So a worker is pretty much a miniature replica of the current BranchAndPrice implementation. One of the workers will be the manager which aggregates data from the various workers. Workers can be different processes on the same machine, or can even run on multiple machines.

To ensure scalability, you don't want to exchange too much information between workers. So an interesting question is: do you want a global column manager which manages the columns of all workers, or do you want a local column manager which only manages the columns of 1 worker? I think the answer to this question should ideally be: let the user decide.
Here's a very interesting article that discusses these issues (Branch, Cut, and Price: Sequential and Parallel):
http://neo.lcc.uma.es/radi-aeb/WebVRP/data/articles/BanchCutPrice.pdf

The next 3 weeks will be insanely busy for me, after that things should revert back to normal :)

[rowtricker]

No problem, I know the feeling.

Ok good:

• I agree, maybe we should add this to ColGen and AbstractBranchAndPrice, such to provide the user with a cleaner API? In this case, there is no need to attach different options to different classes, as all other options are also set by ColGen and AbstractBranchAndPrice. Moreover, it provides more flexibility in case of parallel processing, as in this case a global manager could be passed to different nodes in the search tree.
• That was indeed the idea that I had for the AgingColumnManager. However, I would suggest that the use of this prices is an option set by the user. I will see if it is best to simply make an option for this or to consider two seperate classes.

And for the discussion points:

1. Ok good, I will implement that into AbstractMaster and make removeColumn abstract.
2. That was meant to indicate that the coupling between Master and ColumnManager should not be too strong, as we, for example, do not necessarily want each of the solves in strong branching to be considered as an update to the aging of columns. Hence, a strategy that simply updates at each iteration of Master does not seem a good idea. This warrants an idea as suggested here through method calls.
3. That is what I would also expect. Would you go for an Aging strategy as the default? This does mean that we would need to find a good default parameter setting for the aging. Alternatively, the default could be the current PassthroughColumnManager
4. Agree.

Ok, I will try to take a look at the article if I have some time. The idea of a global manager does seem interesting, especially when one can also use that to price columns. However, there is a need to be careful as not all columns may still be feasible for each node.

[rowtricker]

This mail from the Scip mailing list might also provide some useful ideas when implementing column management in a parallel setting: http://listserv.zib.de/pipermail/scip/2013-October/001688.html