How can I explicitly set the solver for an integer programming problem to use the branch-and-price method in Python code?

[ffgg11]

I have an integer programming instance with 540,000 binary variables and approximately 2 million constraints. I am already aware that the optimal solution to this problem is extremely sparse. I would like to solve it using the branch-and-price algorithm. How can I specify the solver to use branch-and-price?

[Joao-Dionisio]

Hey @ffgg11! This requires a bit of work on your part, as it would be you who needs to implement the master and pricing problems and handle the dual variables. If you think this seems doable and/or fun, there is the branch and price series of exercises over on scipdex: here.

However, I would also seriously consider using something like PyGCGOpt, which is the python interface of GCG (also belongs to the SCIPOptSuite). It stands for Generic Column Generation and is heavily tuned for this. However, you have less control than if you were to implement things yourself.

[ffgg11]

hi @Joao-Dionisio ，Thank you for your response. I am testing PyGCGOpt. But I encountered the following issue:

Exception has occurred: AttributeError
'pygcgopt.gcg.PartialDecomposition' object has no attribute 'maxForWhiteScore'
File "C:\Users~\Desktop\PyGCGOpt-master\src\pygcgopt\decomposition.pxi", line 1433, in pygcgopt.gcg.PartialDecomposition.repr
return f"<PartialDecomposition: nBlocks={self.getNBlocks()}, nMasterConss={self.getNMasterconss()}, nMasterVars={self.getNMastervars()}, nLinkingVars={self.getNLinkingvars()}, maxForWhiteScore={self.maxForWhiteScore()}>"
File "C:\Users~\Desktop\PyGCGOpt-master\PCG_test.py", line 72, in
print(decomps)
AttributeError: 'pygcgopt.gcg.PartialDecomposition' object has no attribute 'maxForWhiteScore'

I have checked the file decomposition.pxi and found that there is no variable or method called maxForWhiteScore. However, there is a similar method called self.max_for_white_score().

So, how should I fix this bug?

[Joao-Dionisio]

I think the people over at PyGCGOpt will be better suited to answer this, I'm not familiar with it, sorry...

[ffgg11]

@Joao-Dionisio HI, Thanks again for your reply.

In solving this large-scale linear integer programming problem, I encountered a following critical issue: In my problem, I have no prior knowledge about a sparse optimal solution. As a result, the linear programming obtained by relaxing the integer programming generates a dense solution. The dense solution of the linear programming causes the solver's branching process to grow exponentially, leading to a failure in solving the problem.

When facing such a problem, SCIP also fails to solve it successfully. Do you have any additional techniques or experience to solve my problem?

[Joao-Dionisio]

The optimal LP solution will always be much denser, but given the information you gave about your model, I'd say that branch-and-price truly is the way to go. Depending on your optimality requirements, I would also investigate heuristics.

Additionally, valid cuts could help immensely, if they're strong enough. This might be more mathematically challenging and require more knowledge about what optimal solutions look like, but the ability to remove large parts of the LP relaxation tends to be very helpful.