2
1

Hi all,

I am trying to solve a lexicographic combinatorial optimization problem by adjusting the incumbent updating and branching rules. And it works, hurrah! At least when CPLEX does not solve the problem at the root node. In that case, of course, CPLEX does not start branching. Does any one know how to explore if there exist multiple optimal solutions? It is a binary program, so I could just use the usual hamming-distance trick, but can CPLEX do it by it self?

edit1: I am actually not interested so much in finding all optima as I am in getting cplex to branch even though bestLB = bestUB.

edit2: The idea is to find a lexicographically smallest solution to the vector optimization problem min{(f1(x),f2(x))|x\in X}, where X is a subset of {0,1}^n. I do this by solving the single objective problem min{f1(x)|x\in X} by a modified b&b algorithm which enumerates all optimal solutions, and returns the optimal solution with the smallest value of f2(x). If a node has LB = UB I would usually just prune the node, as I could not find an improving solution in the corresponding subproblem. However, there might live a feasible solution x in the subproblem with f1(x)=UB but yielding a better value of f2 than the current incumbent does. Therefore I would like to branch further. If the solution is integer feasible, I would create one branch with the extra requirement that

f2(x)< f2(Incumbent)

and if the solution is fractional, I would pick a variable xj and perform the usual branching xj=0 at one branch and xj=1 at the other, but also here require that

f2(x)< f2(Incumbent)

on both branches. Specifically, I would like to branch on the root node, even though it is integer feasible or the integer optimality gap is zero, as there may be multiple optima some with better value of f2 than the first one found.

Kind regards

asked 07 May '14, 09:33

Sune's gravatar image

Sune
958413
accept rate: 20%

edited 12 May '14, 07:57


Assuming that you need to branch at the root node even though CPLEX has found the optimal solution, you could implement an incumbent callback to reject the optimal solution found at the root node. To do so, you would need a way to identify whether you're at root node. I've not tested it before, but I think the getNnodes() method could tell you whether you're at root node or not (it returns the number of nodes processed so far in the active branch-and-cut search).

PS. Beware that using an incumbent callback would disable the dynamic search as well as the deterministic parallel MIP optimization, which might worsen your CPU times.

link

answered 09 May '14, 10:03

Ehsan's gravatar image

Ehsan ♦
4.8k31122
accept rate: 16%

edited 09 May '14, 10:05

The problem with that approach is that the root-node solution might be the lexicographically smallest solution. Therefore I should not reject it.

(12 May '14, 06:29) Sune

Perhaps you could elaborate more on what you do after the root node. Then, we could see whether it is possible to mimic similar behavior in the root node.

(12 May '14, 07:06) Ehsan ♦

of course. I have added edit2 to the original question.

(12 May '14, 07:57) Sune

Since you're optimizing a BIP, you might add an additional constraint that forbids finding a solution that is the same as the root node solution. This way, you have to stop after after finding the optimal solution at the root node, add a cut of the form \(\sum_{i \in J_0} X_i+\sum_{i \in J_1} (1 - X_i) \geqslant 1\) (where, \(J_0\) includes indices of variables set to zero in the root node solution, and \(J_1\) includes indices of variables set to one in the root node solution), and then re-optimize.

(14 May '14, 10:53) Ehsan ♦

Yes, that is the "Hamming distance trick" I mentioned in the question. After reading your first answer again(!) I found a way to do it using the incumbent callback. I simply keep my own structure to save the incumbent and then prune nodes yielding a LB larger than the incumbent. However, internally in CPLEX I reject all integer solutions. This way I have full control over the behavior. I have accepted your answer as it actually was exactly what I needed, it just took some time to realize. Thank you for your time!

(15 May '14, 06:05) Sune

I forgot that you mentioned the hamming distance in your post, but I'm glad that it worked for you eventually.

(15 May '14, 07:18) Ehsan ♦
showing 5 of 6 show 1 more comments
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

Asked: 07 May '14, 09:33

Seen: 2,208 times

Last updated: 15 May '14, 07:18

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