Hello, I am a beginner with IBM ILOG CPLEX and i need an example for a branch and bound code who used CPLEX to resolve the pickup and delivery problem with time windows.

In fact I have already written the code under CPLEX and I tried to test my code with solomon's instance ( C101_m1) and it works very well but when I try with another instance (for example: C102_m1) my code take a long time and he can't resolve the instance so I think that it is necessary to add some constraints of cups(cuttings planes)

NB: I put my files .mod and .DAT as well as the instances of tests " C101 m1 " and " C102 m2 " on this link : https://www.dropbox.com/sh/c6xaf5ythvax0zf/AABKW-elY30da8MaI3ZPjJgfa?dl=0

thanks in advance

asked 02 Sep '15, 11:15

CPLEX1's gravatar image

CPLEX1
1113
accept rate: 0%

edited 04 Sep '15, 02:38

1

What did you try yourself? In what language do you want to code this? Did you write down the Integer Programming model? Did you read the examples shipped with the IBM ILOG Optimization studio suite? Have a look at the three index formulation in the paper "Branch-and-Cut-and-Price for the Pickup and Delivery Problem with Time Windows" by S. Ropke. That model is easy to implement.

(02 Sep '15, 14:29) Joris Kinable

In fact I have already written the code under CPLEX and I tried to test my code with solomon's instance ( C101_m1) and it works very well but when I try with another instance (for example: C102_m1) my code take a long time and he can't resolve the instance so I think that it is necessary to add some constraints of cups(cuttings planes) or to try another method as branch and bound but as I am new in cplex I have no idea how to use a branch and bound with CPLEX

(03 Sep '15, 02:54) CPLEX1

NB: I put my files .mod and .DAT as well as the instances of tests " C101 m1 " and " C102 m2 " on this link : https://www.dropbox.com/sh/c6xaf5ythvax0zf/AABKW-elY30da8MaI3ZPjJgfa?dl=0

thanks in advance

(03 Sep '15, 02:54) CPLEX1

By default, Ilog Cplex uses Branch-and-Bound to solve your problem. Your problem is a Integer Linear Programming problem, not just a Linear Programming problem. By specifying that your variables are binary, Ilog Cplex automatically solves it through Branch-and-Bound. C102_m1 is a hard problem instance; you cannot expect to solve it to optimality with a simple MIP model. Either accept suboptimal results, or implement a stronger approach (e.g. Branch-Bound-Cut or Branch-Price-Cut). Again, read the paper I referenced.

(03 Sep '15, 13:53) Joris Kinable

Btw, it seems that you solve the problem through OPL. As far as I know, you cannot implement a cutting plane procedure in OPL (I may be wrong though, never used OPL). Consider rewriting your solution in Java or C++; both of them give you access to the Cutting Plane API. I still would like to ask you to update your initial post showing what you've done and what it is exactly you are stuck with. Shouting "I need help" isn't particularly useful for other people who stumble upon this post.

(03 Sep '15, 13:56) Joris Kinable

Thank you for your responses and I will look at the paper (if you have a reference for a Java or C++ solution who resolve the problem, I will be appreciate if you could give me the link so I can adapt it to my problem).

and only a last question what do you mean by "a simple MIP model"? sorry but I am a beginner in using CPLEX

(04 Sep '15, 02:46) CPLEX1

For Java/C++ implementations, look at the examples which ship with your IBM optimization studio installation (see examples folder under cplex). Useful links: Cplex getting started manual: http://www-eio.upc.edu/lceio/manuals/cplex-11/pdf/gscplex.pdf or the user manual: ftp://public.dhe.ibm.com/software/websphere/ilog/docs/optimization/cplex/ps_usrmancplex.pdf

The think you've built is called a Mixed Integer Programming model (MIP) model. I would recommend to read some basic literature about integer linear programming.

(04 Sep '15, 13:13) Joris Kinable
showing 5 of 7 show 2 more comments
Be the first one to answer this question!
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:

×231
×191
×190
×14
×10

Asked: 02 Sep '15, 11:15

Seen: 2,803 times

Last updated: 04 Sep '15, 13:13

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