Complexity is More than Just the Number of Constraints

A non-OR colleague recently asked me if one particular optimization model was more complex than another because it had more unique types of constraints modeled on various business rules. I guess in a way it is because by having many types of constraints built for various business rules, the model may be harder for humans to understand.

But when I think in terms of model complexity, I think about how hard the model is to solve. After all, your solver doesn’t care how difficult it was for you to determine how to model a certain business rule. It just cares about the mathematical equations you give it. A constraint that took you days to create may actually be very easy to solve for.

Of course, the perfect example of simple constraints creating complex problems is the Traveling Salesman  problem. This problem only has two constraints: the salesman must visit each town and the salesman must return home at the end. And it is that second constraint, that the salesman must return home, that makes the problem so complex.

How do you define complexity when you are modeling operations research problems? Do you think about computation time and P vs NP? Or do you think about how difficult it will be to model the various business constraints?

This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s