Barrier iterates within the feasible region, therefore when the time limit is enforced (termination_status(model) returns TIME_LIMIT), while the optimal solution is still not found, a feasible solution should be available. Nevertheless, primal_status(model) returns NO_SOLUTION and value(my_x) returns an error.
In order to retrieve the solution at the time of termination, I need to use the gurobi backend:
model = direct_model(Solver)
# ...
x0 = MOI.get(backend(model), Gurobi.VariableAttribute("X"), index(my_x))
This allows me to retrieve the values (and proves that they are somehow availble). However, I am not sure I could use it; I have not fully explored the implications of using direct_model for my application, which involves an iterative approach (Benders’ decomposition type) where several model modifications are required. I understand from the JuMP documentation that direct_model has limitations on the types of modificiations allowed.
I guess my questions are the following:
do I have other options that I have missed?
would Julia (JuMP, MOI or Gurobi) development team consider to ensure that the current solution is available when termination status is TIME_LIMIT?
is this maybe addressed in updated versions of the relative packages?
First of all, Gurobi is capable of solving an LP efficiently given your problem scale at most of the time, so you typically won’t need to set a TimeLimit for an LP, as the problem is convex.
If you just want a feasible solution to your LP, you can call optimize! without setting @objective beforehand. I guess it might be a bit faster.
To query the status upon termination, you should first check primal_status, if its result isn’t FEASIBLE_POINT, then basically Gurobi fails to offer you a feasible solution. You need to check termination_status to help you make inference.
You should be sure, as you are the modeller while Gurobi is merely your consultant.
If you managed to retrieve a set of solutions—no matter it is valid or not—you can immediately make substitutions and see if Ax <= b is satisfied, so you are sure whether the candidate solution is feasible or not.
If primal_status is NO_SOLUTION, then Gurobi did not find a feasible solution to return.
Can you share the solver log that is printed to the screen? This will explain what’s going on.
This allows me to retrieve the values (and proves that they are somehow availble)
There might be something in "X" but it may not be feasible.
development team consider to ensure that the current solution is available when termination status is TIME_LIMIT?
We already support this, if Gurobi has a feasible solution to return. It’s likely that something unusual has happened with your model, but it’s hard to say what without the solution log.
Hi @odow , happy to be in the forum!
Thanks for your reply, as well as @WalterMadelim .
I see, I was taking it for granted that Barrier iterates within the feasible region (but any questions on this regard should probably be addressed outside this forum).
I can share with you some log info of a test case; without the time limit I get
From worker 2: Objective Residual
From worker 2: Iter Primal Dual Primal Dual Compl Time
From worker 2: 0 -2.27855020e+13 7.59873193e+10 4.82e+07 1.15e+05 1.73e+09 2s
From worker 2: 1 -1.48304891e+13 2.26619599e+11 2.04e+07 9.67e+04 1.22e+09 2s
...
...
From worker 2: 45 8.63500450e+09 8.63520764e+09 7.48e-04 3.58e-05 3.70e-01 8s
From worker 2: 46 8.63511695e+09 8.63519290e+09 2.38e-04 2.06e-05 1.38e-01 8s
From worker 2: 47 8.63515735e+09 8.63518326e+09 1.34e-04 1.02e-05 4.73e-02 8s
From worker 2: 48 8.63516991e+09 8.63517709e+09 5.77e-05 2.90e-06 1.31e-02 8s
From worker 2: 49 8.63517137e+09 8.63517643e+09 3.31e-02 2.23e-06 9.24e-03 8s
From worker 2: 50 8.63517267e+09 8.63517514e+09 1.92e-02 7.99e-07 4.51e-03 8s
From worker 2: 51 8.63517350e+09 8.63517476e+09 2.61e-02 4.12e-07 2.30e-03 9s
From worker 2: 52 8.63517419e+09 8.63517445e+09 5.32e-03 1.56e-07 4.75e-04 9s
From worker 2: 53 8.63517436e+09 8.63517438e+09 4.65e-04 3.14e-08 3.08e-05 9s
From worker 2: 54 8.63517437e+09 8.63517438e+09 5.58e-05 3.68e-08 3.83e-06 9s
From worker 2: 55 8.63517437e+09 8.63517438e+09 3.16e-05 2.67e-08 2.20e-06 9s
From worker 2:
From worker 2: Barrier solved model in 55 iterations and 8.98 seconds (13.70 work units)
From worker 2: Optimal objective 8.63517437e+09
and with a time limit at 8seconds, I get:
...
From worker 2: 40 8.61678515e+09 8.63894041e+09 9.79e-02 1.60e-03 4.04e+01 7s
From worker 2: 41 8.62790724e+09 8.63729439e+09 3.88e-02 1.17e-03 1.71e+01 7s
From worker 2: 42 8.63211661e+09 8.63564343e+09 1.54e-02 3.09e-04 6.42e+00 8s
From worker 2: 43 8.63424128e+09 8.63532029e+09 4.41e-03 1.30e-04 1.96e+00 8s
From worker 2: 44 8.63484710e+09 8.63523448e+09 1.47e-03 5.99e-05 7.05e-01 8s
From worker 2: 45 8.63500450e+09 8.63520764e+09 7.48e-04 3.58e-05 3.70e-01 8s
From worker 2: 46 8.63511695e+09 8.63519290e+09 2.38e-04 2.06e-05 1.38e-01 8s
From worker 2:
From worker 2: Barrier performed 46 iterations in 8.00 seconds (12.21 work units)
From worker 2: Time limit reached
Indeed, if I am reading the log info correctly, the increasing values under Primal Objective indicates primal infeasible iterates (for a minimization problem). I will look more into it, many thanks again for your inputs.
Your logging is quite healthy—from both the num of iterations (<60) and wall clock runtime (<9s).
That’s what I told you: typically setting TimeLimit for an LP is not needed.
Gurobi at first analyze your feasibility system—is primal feasible? Is dual feasible?
If your obj === 0, the dual is feasible. But finding a primal feasible point (or giving an infeasibility certificate) is nontrivial—it may take some barrier iterations.
Thanks @WalterMadelim ,
Just to give you a bit of context for my application, the logging I shared regards a toy version where I tested the time limit relevant functionalities. The actual application regards decomposition of a stochastic problem. Each subproblem is a scenario-specific large LP, which requires something less than an hour to be solved with Barrier; however, occassionally, there is one or two subproblems (out of ~50) that take much longer, maybe twice as much. I wanted to brute force a time limit to avoid having CPUs remaining idle while waiting for one scenario to complete, since an “as good as possible” solution would be acceptable at that point of the decomposition algorithm.
What I have learned from this discussion is that Barrier does not necessarily iterate within the primal feasible region (something that I need to clarify, but outside here) and that if the current iterate was a feasible solution Julia would have returned it.
e.g. Maybe you’re tackling a capacity expansion problem in power systems so the subproblems are very large-scale LPs.
This situation is not strange. If I encounter this sort of tough case, I would check the logging of this subproblem solving to ascertain whether Gurobi’s barrier algorithm is functioning properly. It happens occasionally that Gurobi hints me to tune a parameter BarHomogeneous. And since Gurobi will automatically run crossover upon Barrier finishes, you may want to ban Crossover to see if you can make the subproblem runtime shorter.
If you use Benders decomposition w.r.t multiple scenarios, the gap reduction at the global level would proceed well even if you gets stuck at one or two tough subproblems, particularly when the total number of scenarios is large (say, 1e4, 1e5 or larger).
One problem you’ll have to consider seriously is:
Will the Benders cut I added to the master problem be valid? When will it be valid?
You are solving a 2SSP with Min sense. The 2nd stage problem is Min sense, and the 1st-stage decision occurs at the RHS of the constraints of the 2nd-stage problem. If I were you, I’ll explicitly write out the LP dual of the 2nd-stage subproblem so the dual problem is a Maximization. And I solve this dual LP with Gurobi.
Now I claim:
If Gurobi finds a primal-feasible solution for the (Max-sense) dual LP, then the Benders cut constructed at this solution will be valid.
It’s meaningful that in this circumstance you have an opportunity to generate a valid Benders cut even if Gurobi fails to solve that (Max-sense) LP to optimality.
In general, your question here is highly related to difficulties a programmer would meet in reality. Feel free to share the context as it will help elevate our understanding of the real-world challenges.
e.g. Maybe you’re tackling a capacity expansion problem in power systems
You caught me!
Thanks for the suggestions. I will try to track more carefully the barrier log in my full scale runs. Crossover is deactivated already.
I am not using Benders in this particular case (though your suggestions are very interesting and I will definitely come back to those for my Benders applications.)
I want to implement the time limit in the calculation of the wait-and-see solution, i.e. I am solving scenario-specific capacity expansion problems and averaging the output. I use the output to obtain some initial values for my capacity investment variables. Having suboptimal values from one scenario is not an issue.
Actually, at this point feasibility is not much of an issue - other than the fact that I cannot retrieve the values I need unless I use the gurobi backend and direct_model.
Even if those values are out of bounds I can easily bring them back at their limit and still have a good initial point.
