Hi All,

I am trying to learn combinatorial optimization. One of the troubles that I am facing is formulating ILPs. I am looking for any tutorials that can help me reason about writing ILPs. Especially in the context of problems defined on graphs such as TSP, VRP etc...

asked 01 Oct '11, 10:08

Chandrasekhar's gravatar image

Chandrasekhar
312
accept rate: 0%

retagged 26 Nov '11, 14:56

fbahr's gravatar image

fbahr ♦
4.6k716


Check out Model Building in Mathematical Programming by H. Paul Williams.

link

answered 01 Oct '11, 11:21

Luis%20de%20la%20Torre's gravatar image

Luis de la T...
4231612
accept rate: 11%

I agree with Luis de la Torre. "Model Building in Mathematical Programming" is one the best books on the market with three chapters dedicated to ILP modeling. It also has an extensive list of 24 problems discussed and modeled at the end of the book. If you are just interested in routing problems, I recommend checking "Applied Integer Programming: Modeling and Solution" which has devoted a single chapter to TSP and its variants besides the usually discussed problems and ILP modeling tricks.

Finally, I believe you cannot find a single resource which could fulfill your needs completely. I think it's better to read one of the above books and then check the papers, trying to understand what is the main modeling idea.

link

answered 01 Oct '11, 11:37

Ehsan's gravatar image

Ehsan ♦
4.8k31122
accept rate: 16%

There is a book written by Robert G.Jeroslow named "Logic-based decision support mixed integer Model formulation", which can also help you on this topic. Particularly, that book provides a unique view from Jeroslow on modeling and logic in combinatorial optimization

link

answered 02 Oct '11, 15:07

Jiadong%20Wang's gravatar image

Jiadong Wang
704
accept rate: 0%

FICO has a list of standard MIP formulations: http://brblog.typepad.com/files/mipformref-1.pdf

This free brochure covers most of the common MIP logic formulations, abs/max/min functions, converting a binary*scalar multiplication into an MIP formulation etc.

Since your interest is in ILPs, you may not find the MIP stuff useful, but there are sections of the guide that are strictly ILP, notably section 2.1.

link

answered 01 Oct '11, 12:06

Gilead's gravatar image

Gilead ♦
2.3k513
accept rate: 15%

edited 01 Oct '11, 12:11

Nearly all OR introductory textbooks focus on model building/formulations. So i would suggest checking this question. As for "graph problems" most of them have a special chapter devoted in network optimization, transportation problems and so on.

Personally I would discourage digging in scientific papers looking for formulations. At this level they could be confusing and distract you from the big picture.

link

answered 01 Oct '11, 12:12

Florents%20Tselai's gravatar image

Florents Tselai
600516
accept rate: 7%

My own experience with routing problems with time windows was that you could not solely rely on books and tutorials but you should dive into the papers. I should note that I did have a strong background in IP modeling trick before doing so.

@Florenc: I understand your concern. However, my advice was mostly intended for grad-students. Formulations of some problems are really hard to find in books and all the books are not available for every one. Also, Tutorials are not always a good choice as their content and quality highly depends on the writer's knowledge and preferences.

(01 Oct '11, 13:50) Ehsan ♦

My bad. I thought you're an undergraduate looking for a kind of introduction. Since you have "a strong background in IP modeling" there's no problem with scientific papers. In that case, especially for VRP i would suggest some overview articles from Gendreau and Laporte who write papers in a tutorial fashion. For example see this ( http://bit.ly/p4WMg3 ) and "Chapter 6 Vehicle Routing- Handbooks in Operations Research and Management Science,Volume 14, 2007, Pages 367-428 Cordeau, Laporte et. al.

(02 Oct '11, 11:08) Florents Tselai
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:

×127
×101
×29
×28
×15

Asked: 01 Oct '11, 10:08

Seen: 2,162 times

Last updated: 26 Nov '11, 14:56

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