4
1

For many problems, there are multiple ways of modelling them, with different variables and constraints. These different models can have quite different performance characteristics when submitted to solvers.

I'm wondering what resources are out there that address this. Are there algorithms that can automatically transform a model into a "better" form? Is there literature on what types of models are better? Is this what "pre-solvers" do? Are there any descriptions of the algorithms that pre-solvers use?

It seems that certain types of models might be easier for a user to formulate, while others would be easier for solvers to solve. A way to convert between the two would be useful.

asked 23 Oct '11, 19:53

DC%20Woods's gravatar image

DC Woods ♦
4.1k22546
accept rate: 5%

retagged 24 Nov '11, 10:12

fbahr's gravatar image

fbahr ♦
4.6k716


The only model transformation tool I know is called "graduate student". But they take years to train, and as soon as they're able to do the job properly, they get decomissioned. But seriously, modeling is an art (some say, a "black art"). There are many good guidelines for good formulations (mostly learned through the school of hard knocks, as Paul Rubin put it), but ultimately there are very few techniques that work well in all circumstances. The modeler really needs to understand the model and the problem well to pick the right formulation. The process cannot be completely automated.

Also, you'll find that a lot really neat modeling formulations are in fact tricks-of-the-trade and aren't published anywhere. Consultants rely on these for their livelihood, and do not have an incentive to make them widely known. Bear in mind also that some tricks are solver-specific, and also technology specific. New solver technology sometimes renders many tricks obsolete, so even if a trick is published, the next version of CPLEX or whatever may behave in a way as to not benefit from the trick.

That said, I know of two blogs that often publish interesting formulations. These tend to be tricks at the mathematical level, are are less prone to solver peculiarities:

Just a few more references:

All that said, the process of coming up with a good formulation can be "mechanized" to some extent, in the sense that there are tools to help the modeler make informed decisions on the types of formulations to use.

I think I mentioned once that in optimization modeling, the proof of the pudding is in the eating. In most practical situations, there are so many interacting factors that there is no deterministic way of knowing a priori what formulation works best. You just have to try them all out. An algorithm to predict the performance of a formulation on a particular problem may be as expensive or more expensive than solving the problem itself. For instance, when do we use a Lagrangian decomposition? Generalized Benders? All these decisions are usually made based on human experience and intuition, and ultimately trying them out on the problem is to only way to find out for sure. So instead of having tools that tell us what a good formulation is, perhaps we are better served by tools that allow us to experiment with as many formulations as possible? It turns out there is a tool with such a goal.

Pre-solve on the other hand is another kettle of fish. There is a significant amount of academic literature on pre-solve techniques. You can just do a search on Google scholar for them.

http://goo.gl/syI4v

Pre-solve is not my area of expertise, so I'm not able to give you any guidance there. However, there are many folks on this site who have designed pre-solvers (Erling Andersen, Bob Fourer). They may be able to point you in the right direction. It's worth noting that pre-solve routines are usually only able to remove redundancies, tighten bounds, and do little things to make your solver's life easier... but they usually do not modify your problem formulation.

I kind of understand your motivation though. For a long time, I've wondered why no one's ever designed an IDE for optimization problems that gives the user tooltip suggestions on good formulations and warns them about potential modeling pitfalls (sort of like Visual Studio for optimization problems). It's not hard to detect some of the simple common mistakes that people when modeling; the parser logic is usually quite simple (I know because I've written a modeling language).

Or maybe it's already been done? I've only ever used GAMS and AMPL, and I know that at present, neither do this.

-

link

answered 23 Oct '11, 21:45

Gilead's gravatar image

Gilead ♦
2.3k513
accept rate: 15%

edited 25 Oct '11, 11:31

1

Great answer -- accurate and comprehensive. (Also probably the only place -- possibly excluding my obituary -- that I'll see my name used twice with no swear words in between.)

(24 Oct '11, 18:57) Paul Rubin ♦♦
2

Haha Paul you give yourself too little credit. Your posts and answers have helped me tremendously over the years. Your recent one on Benders was really interesting: http://orinanobworld.blogspot.com/2011/10/benders-decomposition-then-and-now.html

(24 Oct '11, 21:28) Gilead ♦

Seconded on the Benders' post.

(25 Oct '11, 10:24) Luis de la T...

By the way, this really is a great answer. This sort of comprehensive response makes the site richer as a resource for people searching for this information in the future, as well as solving my current need for information.

(27 Oct '11, 07:38) DC Woods ♦

Currently, commercial modeling software takes the model as it is and as Gilead mentioned above , we are not sure "when do we use a Lagrangian decomposition? Generalized Benders?". For decomposition methods, we always rely our experiences to decompose the problem. It would be great if we can add a layer under the modeling language to facilitate our reformulation or decomposition. If you find it hard to work inside either AMPL or GAMS since they are commercial softwares. It might be a good idea for people to play with Python-based modeling language like Pulp and Pyomo for research purposes since they are open-source ones. So I guess it is a promising research area, but it is really hard.

link

answered 25 Oct '11, 00:05

Jiadong%20Wang's gravatar image

Jiadong Wang
704
accept rate: 0%

edited 25 Oct '11, 01:57

I'm not positive, but I think I've seen at least one modeling program (Vanguard?) that allows a user to "draw" a flow model using a palette of objects, connecting arrows, and I assume parameters attached to arrows, and turn it into an optimization model (similar to the GUIs for some simulation packages). That's a far cry from converting your "sort of an assignment problem, but with some extra stuff" model into a "sort of a multiple knapsack model, but with some extra stuff", though.

link

answered 24 Oct '11, 18:59

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
14.6k412
accept rate: 19%

Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Tags:

×190
×127
×2
×1

Asked: 23 Oct '11, 19:53

Seen: 1,547 times

Last updated: 24 Nov '11, 10:12

OR-Exchange! Your site for questions, answers, and announcements about operations research.