I use CVXPY with GLPK_MI solver to solve a mixed-integer programming problem. The solver starts with simple simplex, but after some tries, it switches to use "long-step dual simplex" (see the below log file from the solver.) I am wondering when and why GLPK_MI decides to switch its approach? Is there any parameter to change/set this switching point? Is there any way to stop the solver (i.e., with or without optimum solution) after trying simple simplex and before using dual simplex?
Thanks in advance for your time and help!
[21:05:53] [INFO] [dku.utils] - -------------------------------------------------------------------------------
[21:05:53] [INFO] [dku.utils] - Numerical solver
[21:05:53] [INFO] [dku.utils] - -------------------------------------------------------------------------------
[21:05:53] [INFO] [dku.utils] - (CVXPY) Aug 19 09:05:53 PM: Invoking solver GLPK_MI to obtain a solution.
[21:05:53] [INFO] [dku.utils] - (CVXPY) Aug 19 09:05:53 PM: Applying reduction ConeMatrixStuffing
[21:05:53] [INFO] [dku.utils] - 0: obj = 0.000000000e+00 inf = 1.822e+03 (1230)
[21:05:53] [INFO] [dku.utils] - * 4138: obj = -2.197596897e+07 inf = 1.422e-13 (0) 3
[21:05:53] [INFO] [dku.utils] - Long-step dual simplex will be used
[21:05:53] [INFO] [dku.utils] - + 4138: mip = not found yet >= -inf (1; 0)
[21:05:53] [INFO] [dku.utils] - + 4153: >>>>> -2.197593056e+07 >= -2.197593092e+07 < 0.1% (16; 0)
[21:05:53] [INFO] [dku.utils] - + 4153: mip = -2.197593056e+07 >= tree is empty 0.0% (0; 31)
Some guessing:
Dual-Simplex is the default-choice in Branch-and-Cut based search. You really want to use it when solving Integer Programming problems!
Why? Basically because adding cuts or enforcing branching-decisions, things you do in BnC during search usually destroys primal feasibility (you got a primal feasible solution and added a new cut / constraint: it might be infeasible now) and additional work would be needed (to repair feasibility).
In Dual-Simplex, those cuts do not destroy dual-feasibility. You might have lost dual-optimality but can easily continue to optimize here.
Your logs indicate, that the solver changes to dual-simplex exactly in the moment, when branch-and-cut is starting.
Before this, there was no mip indicator and i guess it's about solving the root-node / aka root-relaxation. You could have done that with primal- or dual-simplex. Solver might decide this in terms of problem-statistics (e.g. variables vs. constraint ratio).
But then, BnC starts and the solver will exploit the nice characteristics of the dual-simplex i outlined above.
Your other question do no make much sense to me in general. It's not guaranteed, that you obtained any feasible solution when the switch is happening and i'm not sure what you would do with the root-node solution then.
I mean: you can just drop MIP-based optimization and just solve the LP-relaxation. This is equivalent to Is there any way to stop the solver (i.e., with or without optimum solution) after trying simple simplex and before using dual simplex? in some way... But again... That's not something which makes much sense.
In regards to parameterization, i bet, you can explicitly set the algorithm for those two phases (root-node, BnC search). Consider reading GLPKs documentation which is very complete! (But keep in mind: those solvers are often very good / better as the user in regards to deciding those things for you)