Two Piecewise linear approximation methods has huge performance difference

回答済み

Yize Meng

2021年02月25日 06:56 編集済み

• 
• 
• 

 

 Hi. To approximate a nonlinear fuction, I build two piecewise linear approximation models. Take two dimensional case as an expamle, the first model denotes each point by binary variables Xij, the second model denotes it as continuous variables  pij and adds linear constraints to ensure that pij=Xi*Xj. Thus it can reduce the number of binary variables significantly and I expect it to outperform the first model. However, its running time is about two times of the first one. Is it expected to be so or is there any parameter I can tune to reduce the running time of second model?

The .lp file is in this link with access code m872. 

https://pan.baidu.com/s/1JRRnwxA_UizVj9nL0J3wjw 

0

• 正式なコメント

  

  Simranjit Kaur

  • Gurobi Staff

  2025年06月23日 02:59 編集済み

  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?.
• 

  Jaromił Najman

  • Gurobi Staff

  2021年02月25日 08:59

  Hi,

  Could you elaborate more on the approach you are using? In particular, could you be more precise in the description of which function you are trying to approximate in what way?
  
  Did you try Gurobi's piecewise linear feature? You can model 2D function as described in the Knowledge Base article How do I model a piecewise-linear function of more than one variable?

  When sharing files, could you use one of the services mentioned in Posting to the Community Forum?

  Best regards,
  Jaromił

  1
• 

  Yize Meng

  2021年02月26日 03:03

  • 
  • 
  • 

  Hi Jaromil,

  Thank you very much for your answer， which is really helpful. I realize that my two modeling techniques are just the same as pointed out in the article https://support.gurobi.com/hc/en-us/articles/360039677232-How-do-I-model-a-piecewise-linear-function-of-more-than-one-variable- . In my numerical case it turns out that the alternative way mentioned in the last paragragh of the article outperforms the other way dramatically. It is unexpected.

  0
• 

  Jaromił Najman

  • Gurobi Staff

  2021年02月26日 12:23

  Hi Yize,

  In my numerical case it turns out that the alternative way mentioned in the last paragragh of the article outperforms the other way dramatically. It is unexpected.

  Note that just reducing the number of variables may not be sufficient to improve performance of the optimization. By introducing additional variables, the solver has more possibilities to work with. In particular, it may detect some structure or dependency which it does not see in the smaller formulation. In general, it is very hard to say a priori if a different formulation will perform better or not.

  Best regards,
  Jaromił

  0

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