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?
-
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
サインインしてコメントを残してください。
コメント
3件のコメント