BIP Sensitivity Analysis

[Larry Bonczar]

Hello,

This is more a question about Integer Programming than AMPL, but the answers I receive here will dictate where I go next in my AMPL model. 

I have a BIP model and I have been charged with producing some kind of sensitivity analysis on it. I'm using Gurobi as a solver. The suffix calls provided by the solnsens option for Gurobi result in Gurobi's 1e100 / infinite numbers. In researching why, I've discovered why - the distance between two possible solutions is so great that any ranging on variables in an IP is useless. 

So, when I was taught sensitivity analysis in grad school, it was in the context of Excel based solvers (Palisade @Risk). There, we were taught to build our LP, solve it, then add random noise to the parameters of the model and see how much a random variation in a parameter would affect the optimal solution. Palisade would provide tornado graphs and the like to display the parameters that had the greatest effect. We would then ask practical questions such as under what circumstances would a parameter be likely to change in reality so that the optimal solution given the new parameter would be achieved. This paradigm could allow for IP models; you would just have to ramp up the random noise to get answers. 

In AMPL w/ CPLEX or Gurobi, sensitivity is slightly different; the question is to find out how much a parameter could range before the optimal solution was changed. It's asking sort of the flip side of the same coin as the above; in one, you want to see what will affect the optimal solution; in the other, you want to keep the optimal as is. This coin might very well be double sided in a linear problem, but in an integer they are two very different things it would seem.

In AMPL with Gurobi, are there any practical ways to do a sensitivity analysis on an BIP? Aside from scripting multiple runs of the model with different parameters? 

Thank you, 

[Robert Fourer]

Hi Larry,

I do not know of a way to do sensitivity analysis on a binary integer program except to solve with a variety of different parameter settings. Gurobi does not have any feature that does this for you systematically, so "scripting multiple runs of the model with different parameters" in AMPL would seem to be the necessary approach. It's possible in AMPL to change the parameters either randomly or deterministically.

It seems practical to investigate how much the constraint coefficients or constants could be changed in some way before the optimal objective value changes. However to ask how much of a change can be made before the optimal variable values change is more problematical, since often there are multiple optimal solutions giving the same objective value.

Bob Fourer
am...@googlegroups.com

=======