メインコンテンツへスキップ

Large LP problem

回答済み

コメント

8件のコメント

  • 正式なコメント
    Simranjit Kaur
    Gurobi Staff Gurobi Staff
    This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum. Or why not try our AI Gurobot?.
  • Matthias Miltenberger
    Gurobi Staff Gurobi Staff

    Hi Amin,

    LPs are usually solved until optimality. Gurobi does not provide an easy way to query the best found primal feasible LP solution. You can use the Simplex callback to query the primal and dual violations as well as the current objective value (check the callback example). The solution itself is not accessible, though.

    Please note that you would also need to set the Method to 0 to enforce using the primal simplex, otherwise there might not be any feasible solutions until optimality.

    Did you try some parameter tuning to check whether your LP is really not solvable in an acceptable time frame?

    If you are only interested in a feasible solution, you may also ignore the objective function and solve the feasibility problem:

    f = model.feasibility()
    f.optimize()

    Cheers,
    Matthias

    0
  • Amin Ahmadi
    Gurobi-versary
    Curious
    First Comment

    Thanks for your explanation. I have a general question. In my case, building the lp model is taking too much time ( more than 3000 seconds). I am seeking a way to generate the model in a short time. Do you have any suggestions to generate a model in a reasonable time?

    0
  • Alison Cozad
    Gurobi Staff Gurobi Staff

    You can find some suggestions to speed up your model build here:  How do I speed up the time to build my model?

    0
  • Reshma Chandrasekharan
    Gurobi-versary
    First Comment

    Is there an easy way to do this with the latest Gurobi versions? I am trying to solve an LP model and I wish to obtain the best LP solution obtained within a given time limit.

    0
  • Alison Cozad
    Gurobi Staff Gurobi Staff

    Are you looking to improve your model-building time or solver runtime?

    0
  • Reshma Chandrasekharan
    Gurobi-versary
    First Comment

    Neither. I am trying to solve very large LPs and I wish to know how long I should run them in order to obtain reasonably good solutions. For this purpose, I want to retrieve the best feasible LP solution found so far at different instances of time during the solving process.

    0
  • Alison Cozad
    Gurobi Staff Gurobi Staff

    You are on the right path by considering experimenting with your model.  This is because there is no way to predict how long it will take to retrieve a feasible or optimal solution.  If everything else is the same, typically, models with more variables and constraints will take longer to solve. Yet, this is not always true.  There are seemingly simple small models that are not solved to this day. And some large models can be solved quite quickly.  There are also other factors that play a role, such as the sparsity, structure, and numerics of the model.  We have more details on this in What is the correlation between problem size and solution time?

    It seems like you are looking to do some experimentation on your model or perhaps model instances.  This is exactly the path we would recommend to estimate how long it takes for this particular model to reach an optimal solution. We would typically recommend collecting a few instances of your model and testing how long it takes to solve to optimality. 

    However, you are looking to grab intermediate LP solutions.  To access intermediate solutions or the best feasible LP solution obtained thus far, it is a bit more tricky. You can view the current Simplex candidate.  To do this,

    1. Disable presolve by setting Presolve=0 when using the Simplex algorithm. To access variable solution values after the customized termination in 2, you must have Presolve turned off. This is due to the need to "uncrush" the solution when Presolve is active, which involves transforming it back to the original problem. It's important to note that solving models without presolve can have a significant impact on performance.
    2. Next, you will need to use callbacks to monitor primal infeasibility within the simplex method. Stop the process when a certain level of primal feasibility is achieved. Additional information on this approach can be found in Limit solutions for an LP.
    0

投稿コメントは受け付けていません。