Given some minimisation ILP or MILP defined in CPLEX using Concert in C#, I wish to find a lower and upper bound to the model.

The lower bound can, of course, be found by solving the linear relaxation (ignore integrality constraints). The upper bound can be found by running a heuristic. CPLEX has three general-purpose MIP heuristics that I know of: Node heuristic, RINS heuristic, and Solution polishing. There are parameters in CPLEX for how often to run these heuristic, i.e. every n nodes.

I am having some difficulty just getting an upper and lower bound. Even if I set the NodeLim parameter to 0, CPLEX spends a significant amount of time at the root node. I'm not sure what it's doing, perhaps applying cuts or trying to improve the best bound. I don't want it to do any of this: I just want the optimal value for the linear relaxation at the root node, and some good initial upper bound.

What is the process for obtaining these values in CPLEX using Concert in C#? Thank you.

asked 05 Aug '15, 00:02

Ozzah's gravatar image

Ozzah
3929
accept rate: 0%


When you solve the problem as a MIP with root node bound equal to 0, CPLEX will solve the LP and apply cuts. Although you can disable all these cuts, the easiest way is to replace all integer variables by continues variables. To do this without rewriting your model, I recommend using the IloConversion class. This class allows you to temporarily 'override' the definitions of your variables. CPLEX will not apply any cuts when all variables are continues. As a result, you'll solve a pure LP. Note however that, depending on the size of your problem, just solving an LP may be expensive.

Assuming that your problem is a minimization problem, then the upper bound is simply a feasible solution to your problem. Note however that, the decision problem "does there exist at least one feasible solution to my problem" may already be a very hard problem. In fact, this can be as hard as solving your problem to optimality. Furthermore, for certain optimization problems, Mixed Integer Programming is great for calculating bounds, but not particularly good in producing feasible solutions. In contrast, Constraint Programming often produces good primal feasible solutions, but struggles in providing strong bounds on these solutions.

So in summary, without knowing what you try to solve, it is rather difficult to make good suggestions.

link

answered 05 Aug '15, 13:50

Joris%20Kinable's gravatar image

Joris Kinable
3381213
accept rate: 16%

The Conversion method works well to find the LB via linear relaxation. I haven't found any way to enumerate all variables in the model, so I have to keep track of them manually in code. Is there a better way? As for the UB, yes I know it can be just as hard as finding an optimal solution. In most practical cases, however, a feasible solution can be found somewhat quickly, at least by my experience. Is there any way to invoke Node Select or RINS Heuristic manually? Right now I just set IntSol to 1 and then either just use that solution or use the Polishing heuristic on that.

(07 Aug '15, 09:25) Ozzah

You can iterate over the variables, but it's a bit inefficient. See Paul's blog post for details: http://orinanobworld.blogspot.com/2010/08/iterating-over-cplex-model-sequel.html Easier to keep track of your variables. I usually do something like this:

Map<edge, ilointvar=""> vars=new LinkedHashMap<>();

...

IntVar[] varsArray=vars.values().toArray(new IloIntVar[vars.size()]);

double[] values=cplex.getValues(varsArray);

List<edge> usedEdges=new ArrayList<>();

int index=0;

for(Edge e : vars.keySet()){

if(doubleToBoolean(values[index]))

usedEdges.add(e);

index++;

}

(07 Aug '15, 18:34) Joris Kinable

Thanks, I saw that blog post already but the C# API doesn't seem to expose an Iterator method. There is a GetEnumerator() method, but it only enumerates over the objective function and constraints. I haven't tried to go deeper to see if I can enumerate over the terms in the constraints.

(09 Aug '15, 19:05) Ozzah
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:

×191
×21
×8
×5
×5

Asked: 05 Aug '15, 00:02

Seen: 2,828 times

Last updated: 09 Aug '15, 19:05

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