1
$\begingroup$

Problem Context: I'm working on a large-scale Linear Programming (LP) problem containing over 6 million variables (There are a total of 7 different models). My goal is to improve the model's optimization time.

Analysis Performed: When analyzing the Gurobi and CPLEX logs, I identified two main issues:

Significant reduction in the number of variables by the presolver - The presolver is eliminating a considerable number of variables, which makes me question whether I can optimize the model from its initial formulation.

Numerical conditioning problem - The logs indicate that the model has conditioning issues.

My Questions:

Regarding the presolver: I thought about comparing the post-presolver . lp file with the initial model to identify which variables are being eliminated. The idea would be to analyze whether I can avoid creating these variables from the start, thus reducing the model size before optimization even begins. Does this approach make sense? Is there a more efficient way to perform this analysis?

Regarding the ill-conditioning: I would like guidance on how to identify the causes of ill-conditioning and what techniques you recommend to address this issue. What are the best practices for handling this type of problem in large-scale LP models?

Reading time = 183.38 seconds
: 862106 rows, 3277568 columns, 57976445 nonzeros
Set parameter Presolve to value 2
Gurobi Optimizer version 12.0.3 build v12.0.3rc0 (win64 - Windows 11.0 (26100.2))

CPU model: 13th Gen Intel(R) Core(TM) i7-13850HX, instruction set [SSE2|AVX|AVX2]
Thread count: 20 physical cores, 28 logical processors, using up to 28 threads

Non-default parameters:
Presolve  2

Presolve a model with 862106 rows, 3277568 columns and 57976445 nonzeros
Model fingerprint: 0x8ffe011d
Coefficient statistics:
  Matrix range     [1e+00, 1e+04]
  Objective range  [5e-03, 2e+04]
  Bounds range     [1e+00, 5e+04]
  RHS range        [2e-03, 1e+05]
Presolve removed 834388 rows and 3115632 columns (presolve time = 5s)...
Presolve removed 834763 rows and 3115632 columns
Gurobi Optimizer version 12.0.3 build v12.0.3rc0 (win64 - Windows 11.0 (26100.2))

CPU model: 13th Gen Intel(R) Core(TM) i7-13850HX, instruction set [SSE2|AVX|AVX2]
Thread count: 20 physical cores, 28 logical processors, using up to 28 threads

Non-default parameters:
Presolve  2

Optimize a model with 862106 rows, 3277568 columns and 57976445 nonzeros
Model fingerprint: 0x8ffe011d
Coefficient statistics:
  Matrix range     [1e+00, 1e+04]
  Objective range  [5e-03, 2e+04]
  Bounds range     [1e+00, 5e+04]
  RHS range        [2e-03, 1e+05]
Presolve removed 834388 rows and 3115632 columns (presolve time = 5s)...
Presolve removed 834763 rows and 3115632 columns
Presolve time: 5.50s
Presolved: 27343 rows, 162310 columns, 3128771 nonzeros

Concurrent LP optimizer: primal simplex, dual simplex, and barrier
Showing barrier log only...
Improve this question
New contributor
Lucas Tayrone Moreira is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$
6
  • 1
    $\begingroup$ Can you please provide a mathematical formulation for the model that corresponds to the log? $\endgroup$ Commented 14 hours ago
  • $\begingroup$ Unfortunately, the company does not have an updated mathematical model and does not allow me to post the 10-year-old model they have. $\endgroup$ Commented 14 hours ago
  • 1
    $\begingroup$ For the numerics, you have very different orders of magnitude in your coefficients, in your objective, for example. This creates numerical issues when adding these numbers together. A common approach is to scale some of the variables. Eg, if one variable is measured in dollars, maybe changing it to thousands of dollars makes sense. $\endgroup$ Commented 14 hours ago
  • $\begingroup$ Regarding the presolving: yes, most likely the model has some deficiencies. It might be difficult to discover what the solvers are doing behind closed doors, but your idea of investigating the presolved problem makes sense. $\endgroup$ Commented 14 hours ago
  • $\begingroup$ The whole presolve takes 5s. As already mentioned by João, look at the model coefficients. Are you using BigM? Do you use large numbers to fill missing values or ub? (e.g., using 100M to indicate an upperbound of a variable, etc). $\endgroup$ Commented 13 hours ago

2 Answers 2

Reset to default
0
$\begingroup$

Regarding the presolver: I thought about comparing the post-presolver . lp file with the initial model to identify which variables are being eliminated. The idea would be to analyze whether I can avoid creating these variables from the start, thus reducing the model size before optimization even begins. Does this approach make sense?

No, in general you cannot use names to infer relationships between variables and constraints in the presolved model with those in the original model - (an exception possibly being trivial models).

Regarding the ill-conditioning: I would like guidance on how to identify the causes of ill-conditioning and what techniques you recommend to address this issue.

https://gurobi-modelanalyzer.readthedocs.io/en/latest/

The logs indicate that the model has conditioning issues.

The coefficient stats in the log look ok to me. What signs of numerical issues are you seeing? (https://docs.gurobi.com/projects/optimizer/en/current/concepts/numericguide/modelissues.html)

Improve this answer
$\endgroup$
3
  • $\begingroup$ It's not very clear. I have a set of variables that are created and well identified. If the pre-solver always eliminates a set and I can compare the .lp files and identify where the eliminations occurred and how they were filled in, couldn't I eliminate them? Isn't the pre-solve eliminating them from the model? $\endgroup$ Commented 13 hours ago
  • $\begingroup$ The names do not necessarily refer to the same variable in both models. You can assume they do, and use it as a clue to help you identify opportunities to explore, but I wouldn't put much faith in it. $\endgroup$ Commented 12 hours ago
  • $\begingroup$ More details here: support.gurobi.com/hc/en-us/articles/… $\endgroup$ Commented 12 hours ago
0
$\begingroup$

As mentioned in the comments, ill-conditioning is likely caused (at least in part) by the range of magnitudes of coefficients in the model. Rescaling some variables (e.g., going from grams to kilograms or vice versa) might help. If using a big-M model, either trying more conservative values of M or switching to indicator constraints might help.

Another possible cause of extended solution time, which might not pop up in diagnostics, would be symmetry. Is it possible/likely that, given a feasible solution, you could get another feasible solution with the same objective value by permuting the indices of a variable? For example, if the problem involves a set of machines (with some variables having an index identifying a specific machine), and if all machines are identical, then given any solution you can get another with same objective value by relabeling the machines (machine 1 becomes machine 2, machine 2 becomes machine 3, ...). If the model does suffer from symmetry, you can either try tweaking the solver parameters related to symmetry handling or look for a formulation that avoids the symmetry (perhaps by adding constraints to break the symmetry).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.