Simplex performs worse under looser termination condition
回答済みHello,
I've been using the simplex method (method=0 or method=1), for solving linear programming problems. However, I observed that setting a lower tolerance (e.g., FeasibilityTol=OptimalityTol=1e-8) resulted in faster convergence compared to a higher tolerance (e.g., FeasibilityTol=OptimalityTol=0.0001). This outcome seemed counterintuitive, especially considering the general expectation that looser tolerances might lead to quicker solutions due to fewer stringent checks. Did the observations make sense or what could be the problem?
-
正式なコメント
This post is more than two 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 try Gurobot, our chatbot interface offering instant, expert-level support. -
Hi Jinwen,
Did you run you comparison across many values of Seed? Comparing a single run each under these parameters is problematic as the solution path can change, and any perceived improvement may just be incidental.
- Riley
0 -
Hi Riley,
Thanks for your response. I ran a large batch of LP instances by dual simplex (method=1) but it turns out only half of them with FeasibilityTol=OptimalityTol=0.0001 are faster than those with FeasibilityTol=OptimalityTol=1e-8. The similar observation holds for primal simplex (method=0). Is it due to the randomness, or looser tolerance itself may lead to bad iterations?
0 -
Hi Jinwen,
I'd guess it is randomness, either from other processes inducing load on the machine (in the case of very short solve times) or from different "solution paths" (the decisions that the solver is making under the hood, influenced in part by the value of Seed parameter).
The best comparison would be one using boxplots, or some other method of graphically characterizing distributions of results.
- Riley
0
投稿コメントは受け付けていません。
コメント
4件のコメント