CPLEX comes with a good tool to do tuning that allows the modeler to set which algorithm to use for the problems of a certain structure/type. But outside of the tuning tool are there any rules of thumb or relationship between the kind of problems and the best algorithm suiting them and that too just for LPs with just continuous variables? I am talking about primal, primal devex, dual, dual steep1, dual steep2 etc..

I am observing that the subproblem in my implementation of Benders Decomposition performs faster with primal simplex method in the beginning few iterations, and then towards later iterations dual simplex performs better. All that is changing in the sub problem is the right hand side of a subset of constraints.

asked 18 Jan, 02:38

Naveen%20Divakaran's gravatar image

Naveen Divak...
7418
accept rate: 25%

edited 18 Jan, 08:29


I'm not sure how reliable these "rules of thumb" are, and they're my understanding (not necessarily accurately remembered).

  • If an LP is seriously degenerate, dual simplex may be better than primal simplex, and an interior point method might be better still.
  • If you are repeating an LP but changing the right-hand side in a way that makes the previous solution superoptimal (e.g., you tightened a resource constraint), you'll likely want to use dual simplex.
  • If the changes preserve feasibility of the previous solution but make it suboptimal (e.g., you loosened a resource constraint), I think you may well be better of with primal simplex. (Both this and the previous recommendation assume you are hot-starting the modified problem.)
  • If you made lots of seemingly random changes to the right-hand side, your best bet might be to start from scratch (no hot start) with whatever method worked best on the original problem. (Note that hot starts are enabled by default in CPLEX.)

For MIPs, I only have two rules of thumb. The first is that CPLEX is usually smarter than I am. By "usually" I mean "almost always". The second is that the node log sometimes gives hints. If optimal or near optimal solutions show up early but the bound moves slowly, consider parameter settings that emphasize bound improvement. If it takes a long time to get a good solution, consider parameter settings that encourage CPLEX to dive more deeply or apply search heuristics more frequently to get better primal solutions.

link

answered 23 Jan, 15:49

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
14.5k412
accept rate: 19%

Thanks for the answer. It matches with what I see when I choose different algorithms. For sure these are not hard and fast rules.

(23 Jan, 16:03) Naveen Divak...
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:

×192
×34
×6
×3

Asked: 18 Jan, 02:38

Seen: 174 times

Last updated: 23 Jan, 16:03

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