HiGHS for column generation

[andrea-cassioli-maersk]

Hi,
I am considering HiGHS for to implement a column generation approach, but it is unclear to me how I should proceed.

For what I can see the way is to

• create the master problem as a HighsModel
• solve the master and so on (pricer...)
• add new columns using addColumns (is it the efficient way?)
• solve the master again using warm start

the last point is what troubles me the most:

• how does HiGHS knows the model has changed?
• how do I make sure HiGHS warm starts?
• Shall I save the basis and last solution and feed it back?

[jajhall]

That makes about four projects that I know of using HiGHS for column generation!

What you described is correct and will be efficient. If you add columns using 'Highs::addColumns' then HiGHS will automatically update its internal basis - the new columns will be nonbasic - and won't even have to refactor the basis matrix when you next call 'Highs::run'.

You're talking as if you'll be solving the master with simplex. There is a strong argument to use interior point, since that yields a possibly valuable stabilisation of the dual values. The downside is that interior point doesn't hot start.

[andrea-cassioli-maersk]

@jajhall yeah, we focus on primal simplex, but we could experiment with IP as well.

Is 'Highs::addColumns' part of the model or the solver? I cannot really find a complete documentation of the various interfaces...

[jajhall]

There isn't great documentation for HiGHS. In terms of concepts, start from
https://ergo-code.github.io/HiGHS/dev/guide/basic/
and in detail, look at the C documentation
https://ergo-code.github.io/HiGHS/dev/interfaces/c/

What language are you using?

The "incumbent" model and solvers are tightly integrated, and I can see that causes confusion. So, when you call a model modification method like Highs::addColumns the columns are added to the incumbent model, and accommodated (when possible) within any solution information that is known.

[andrea-cassioli-maersk]

We use C++. So from the cpp example I see that

• one creates a HighsModel model;
• then pass the a Highs solver instance
• the run it.

So you will call addColum on the solver, not on the model?

[jajhall]

What you understand is correct for building, passing and solving a model, but there is no distinction between the model and the solver: the model data and are data members of the Highs class, as are the solver data. So, when you call addColumns, both model and solver data will be modified

I don't understand the distinction that you're trying to make

[guifcoelho]

Following this topic, recently I've managed to build a column generation and branch-and-price algorithm using Highs's python interface and I would love to add it as an example. Would you be interested?

[jajhall]

Wow! That's great to hear!

Yes, we're not Python programmers, so some significant Python-based use of HiGHS would be interesting to have.

[guifcoelho]

Great! I will get it ready ASP.

[andrea-cassioli-maersk]

I am looking at a CG for a huge LP, so maybe I am in a simpler spot...a good example is more than welcome!

[guifcoelho]

Hello, I've added an issue and submitted a new pull request with the branch-and-price example. As a somewhat minimal example I think it's fine, but I'm sure that there is space for improvement, specially at the branching part. In any case, please take a look and let me know if any changes are required.

[jajhall]

The Python branch-and-price implementation has been pushed to 'master'