Computational cost between variable bound constraints and inequalities constraints

[문재영]

Hi, everyone.

I'm Jeayoung Moon. And I'm a student on Yonsei Univ. in South Korea.

And I have a question about computational cost between variable bound constraints and inequalities constraints.

I set my mods on AMPL.

For example,

One is about variable bound constraints as below:

var aij{i in I,j in J} >= -amax, <= amax;

and the other is about inequalities constraints.

var aij{i in I,j in J}

s.t Bound_upper_a {i in I,j in J}:

aij[i,j]<= amax;

s.t Bound_lower_a {i in I,j in J}:

aij[i,j]>= -amax;

When I solve these problems, there are huge differences on computational cost on CPU. (But the solutions are same.)

I wonder why the different result came out.

And want to know the reason logically or deeply.

Please, help me to know that. Or let me know some academic references to read.

Thank you very much!!

[Victor Zverovich]

AMPL presolve should eliminate the constraints Bound_upper_a and Bound_lower_a so the solver will only see variables with bounds [-amax, amax] in both cases unless you disable presolve. AMPL processing time for the second case is likely to be larger because it needs to instantiate additional constraints and presolve has to do more work.

HTH,

Victor

--
You received this message because you are subscribed to the Google Groups "AMPL Modeling Language" group.
To unsubscribe from this group and stop receiving emails from it, send an email to ampl+uns...@googlegroups.com.
To post to this group, send email to am...@googlegroups.com.
Visit this group at https://groups.google.com/group/ampl.
For more options, visit https://groups.google.com/d/optout.

[문재영]

Thank you for your reply!

I got your reply and I can understand AMPL has the presolve process.

But if the presolve process is disable, I think AMPL processing time for each case is still different.

I still have a wonder about computational cost between variables with bounds and inequalities constraints.

I mean why variables with bound and equalities/inequalities constraints are different on processing time. (even though there are same number of constraints)

I wonder why and where the difference occurs.

Could you help me to know more or let me know some references to read ?

TIA

Jaeyoung

2016년 7월 27일 수요일 오전 4시 0분 37초 UTC+9, Victor 님의 말:

[e.d.an...@mosek.com]

As a solver vendor i.e. MOSEK I normally tell our customers the following.

Whether you use bounds or explicit constraints does not make difference on the optimizer time. However say you have a model with a huge number variables and almost no constraints, then presolve time in the optimizer can be significant.

So if you care a lot about efficiency it is normally better to use bounds.

Btw I doubt you can get a textbook answer to your question because the answer depends on how things are implemented. Comparing the options is likely to be way to go for a definite answer.

[문재영]

Thank you for your reply!

I searched 'presolve' on AMPL Book, 

And now I can understand how the presolve process works.

I think my question is little vague and my English is poor to present my whole question. I'm sorry.

Let me show you another extreme example.

There are two cases below:

One is about variables with bound:

var aij{i in I,j in J} >= -amax, <= amax;

and the other is about inequalities constraints:

var aij{i in I,j in J}

s.t bound_a {i in I,j in J}:

(aij[i,j])^2<= (amax)^2;

These cases are equivalent, but the second one is not eliminated by the presolve process. I set the second one on purpose to compare the two cases.

And It takes much computational cost. (CPU time)

I know empirically it is better to use bounds.  

I mean I wonder 'why' inequalities constraints are much computational than variables with bound.

TIA

Jaeyoung

2016년 7월 27일 수요일 오후 9시 47분 27초 UTC+9, e.d.an...@mosek.com 님의 말:

[e.d.an...@mosek.com]

This

    (aij[i,j])^2<= (amax)^2;

is nonlinear expression. Everything tends to be less efficient on nonlinear stuff. This typically includes presolve

You should do

    -abs(amax) <= aij[i,j] <= -abs(amax)

I thought you compared this bound constraints.

[You could also have done 2log((aij[i,j]))<= 2*log((amax)) so there are many obscure ways of specifying symmetric bounds. Some of them might not be discovered by the system and hence you cannot expect them all to behave the same.]

[문재영]

Thank you for your reply!

I understood what you explained. And I learned reformulations are important.

-Jaeyoung

2016년 7월 28일 목요일 오전 12시 19분 27초 UTC+9, e.d.an...@mosek.com 님의 말: