16110https://www.ibm.com/developerworks/community/forums/atom/replies?topicUuid=e006d18b-7f75-4463-ae57-f1651c188462No proof of optimality Replies2013-08-12T15:54:15.358ZIBM Connections - Discussion Forumurn:lsid:ibm.com:forum:d2825d88-253e-4339-897d-ec9fd2a5adfeRe: No proof of optimality2013-08-12T15:54:15.358Zazak 270004FD3Nactive2013-08-12T15:54:15.358Z
<p dir="ltr">
Thank you very much, Daniel! I have just sent you the files and will be looking forward to your reply.
</p>
none, view_forum, view_categoryurn:lsid:ibm.com:forum:72b26458-c9eb-4a29-ac69-fc32ea803865Re: No proof of optimality2013-08-12T07:16:37.885ZDanielJunglas270002S4SXactive2013-08-12T07:16:37.885Z
<p dir="ltr">
Would you be willing to post a .mod and .dat file for the problematic graph here? Then we could try to take a quick look at what CPLEX is doing (or what if fails to do) with this model and check if there is something obvious to improve.
</p>
<p dir="ltr">
If you don't want to post the files in public you can also send them directly to me: daniel(dot)junglas(at)de(dot)ibm(dot)com.
</p>
none, view_forum, view_categoryurn:lsid:ibm.com:forum:45506eb2-4e99-4fce-bcc5-6e9cc0363688Re: No proof of optimality2013-08-08T16:26:12.123ZEdKlotz270002TE51active2013-08-08T16:26:12.123Z2013-08-08T16:29:58.203ZEdKlotz270002TE51active
<p dir="ltr">
That clarifies things a bit. I'll try to have a closer look at the formulation involving the second objective and reusing colors. Meanwhile, based on your description, you might be able to find additional solutions by running CPLEX's RINS heuristic every 100 nodes or so. This is a local search heuristic, which makes sense for a model like this. It certainly seems possible that you can find better solutions by adjusting the colors on fairly small subsets of nodes in the graph, and local search heuristics like RINS can detect such improvements. However, while that may find better solutions, it probably won't help proving optimality in this case. In that regard, I recommend
</p>
<ul dir="ltr">
<li>
Read the paper Daniel mentioned about formulating this problem without symmetry. Even if you decide that you don't want to use that formulation (e.g. because it doesn't extend to the color reuse activities), it may shed light on how to apply symmetry breaking constraints to your existing formulation.
</li>
<li>
Look for other opportunities to tighten the formulation. Daniel already mentioned cuts involving cliques in your graph, since each vertex in a clique must have a separate color. Look for other subgraphs that might yield something useful. In some ways, it seems like vertex coloring is well suited to some sort of decomposition scheme. After all, if you can show that a particular subgraph needs n colors, connecting that subgraph to other vertices in the original graph can only increase the colors needed.
</li>
<li>
Regarding parameter settings, at least for the first objective, try setting CPLEX's clique cut generation to its most aggressive setting of 3.
</li>
</ul>
none, view_forum, view_categoryurn:lsid:ibm.com:forum:2070092b-f182-45e9-9874-4e28592ff068Re: No proof of optimality2013-08-08T15:42:40.441Zazak 270004FD3Nactive2013-08-08T15:42:40.441Z
<p dir="ltr">
Thank you for the insights!
</p>
<p dir="ltr">
1. Yes, it's redundant but I noticed shorter solving time (when the runs are not the problematic ones).
</p>
<p dir="ltr">
2. This is a way to eliminate nonlinearity x[i][k]*x[j][k]=1, but instead of using (x[i][k]+x[j][k])/2 >= c[i][j][k] I split it into 2 inequalities hoping that this will make it tighter.
</p>
<p dir="ltr">
3. True, this already limited by the NbColors set.
</p>
<p dir="ltr">
4. You are right, this is a valid inequality. I added this and precalculated min sum of a(i) as well as weight of the vertices with reused colors (as in the reply to Ed) yet still no effect on the bound.
</p>
<p dir="ltr">
I'm going through the papers you recommended looking for cut inspirations. The formulation deals well with the basic coloring constraints, just added one small extension and yet this poses so many problems. Will also have a look into soft constraints as suggested by Ed.
</p>
<p dir="ltr">
I'm quite new in this area and there is plenty of things to learn so I greatly appreciate your tips!
</p>
none, view_forum, view_categoryurn:lsid:ibm.com:forum:b2f38eae-b4bb-4628-bdb3-13f881143832Re: No proof of optimality2013-08-08T13:33:33.546Zazak 270004FD3Nactive2013-08-08T13:33:33.546Z2013-08-08T15:52:03.561Zazak 270004FD3Nactive2013-08-08T13:33:33.669Z2013-08-08T13:33:33.669Z2013-08-08T13:33:33.938Z2013-08-08T13:33:33.938Z2013-08-08T13:34:50.682Z2013-08-08T13:34:50.682Z2013-08-08T13:34:50.801Z2013-08-08T13:34:50.801Z
<p dir="ltr" style="margin-bottom:0.0001pt;">
<span style="font-family: 'courier new';">Thank you for the comments, I'm sorry if it was unclear, I'll try to explain in more details.</span>
</p>
<p dir="ltr" style="margin-bottom:0.0001pt;">
</p>
<p dir="ltr" style="margin-bottom:0.0001pt;">
<em><span style="font-family:courier new;">>>So, how did the node log you attached have a zero objective, not only for the root, but for many subsequent nodes in the optimization? Were you using your second objective?</span></em>
</p>
<p dir="ltr" style="margin-bottom:0.0001pt;">
<span style="font-family: 'courier new';">Yes, that is for the second objective. In general the problem is easily solvable if we have high K, which results in either the optimal number of colors (obj1) or 0 (obj2) as all the a variables are set to 0. In the example that I use for analysis here, the optimal number of colors to satisfy regular and group constraints is 10 (solving obj 1- log_bigK_o1).</span>
</p>
<p dir="ltr" style="margin-bottom:0.0001pt;">
<span style="font-family:courier new;">The challenge start when we decrease the number of colors in such a way that diffNeighColor is still satisfied but some a(i) are forced to 1. Hence, the obj1 should be at least NbColors whereas obj2>0.</span>
</p>
<p dir="ltr" style="margin-bottom:0.0001pt;">
</p>
<p dir="ltr" style="margin-bottom:0.0001pt;">
<em><span style="font-family:courier new;">>>If so, can you post a log for a challenging model for the first objective?</span></em>
</p>
<p dir="ltr" style="margin-bottom:0.0001pt;">
<span style="font-family:courier new;">Yes, attached as log_smallK_o1. The optimal number of colors is 10, I decreased to 9 (the bound could be 8 if some vertex weights are 0). Even more, I know that by reducing by 1 color, some of the groups will reuse a color. Summing the min weights of vertices in such groups I get 2.5518, so min value of obj1 is 10.5518 (2.5518 for obj2). </span>
</p>
<p dir="ltr" style="margin-bottom:0.0001pt;">
</p>
<p dir="ltr" style="margin-bottom:0.0001pt;">
<em><span style="font-family:courier new;">>>I'm not completely clear on the second objective; is it trying to minimize the sum of reused colors in a group that allows violations of the basic unique color requirement for edges? </span></em>
</p>
<p dir="ltr" style="margin-bottom:0.0001pt;">
<span style="font-family:courier new;">It allows violations and reuse a color within the group (among the vertices that are not connected), so it still keeps the basic unique requirement for edges (diffNeighColor).</span>
</p>
<p dir="ltr" style="margin-bottom:0.0001pt;">
</p>
<p dir="ltr" style="margin-bottom:0.0001pt;">
<em><span style="font-family:courier new;">>>If I correctly understand your second objective, I am not particularly surprised that the model with the second objective is more difficult to solve for a branch and cut solver like CPLEX than the first. You are introducing some soft constraints with the second objective. Soft constraints can weaken a formulation in the sense that certain infeasibilities that previously could be used to derive cuts no longer are available. Think about it this way; if you had a knapsack constraint, you initially might be able to deduce numerous cover cuts. But, if you soften it by subtracting a surplus variable, you remove those cover cuts. The same thing applies for your model with clique cuts.</span></em>
</p>
<p dir="ltr" style="margin-bottom:0.0001pt;">
<em><span style="font-family:courier new;">>>So, are most of your performance difficulties occurring with the second objective, or do you have them with the first objective as well? I'd really like to see a node log from a problematic run using the first objective, as I now have concluded the log you sent above involves the second objective, not the first.</span></em>
</p>
<p dir="ltr" style="margin-bottom:0.0001pt;">
<span style="font-family:courier new;">Yes, the log attached before is with obj2.</span> <span style="font-family:courier new;">I have the problem with obj1 objective as soon as any of a[i] is set to 1 (previously mentioned log log_smallK_o1)</span>
</p>
<p dir="ltr" style="margin-bottom:0.0001pt;">
</p>
<p dir="ltr" style="margin-bottom:0.0001pt;">
<em><span style="font-family:courier new;">>>Regarding models with the second objective, try solving an auxiliary model where you minimize just the sum of the reuse variables. </span></em>
</p>
<p dir="ltr" style="margin-bottom:0.0001pt;">
<span style="font-family: 'courier new';">I changed the second objective also to</span>
</p>
<p dir="ltr" style="margin-bottom:0.0001pt;">
<span style="font-family:courier new;">O3: sum a(i) (log_smallK_o3) the bound doesn't move from 0 and I know that the optimal value is 28.</span>
</p>
<p dir="ltr" style="margin-bottom:0.0001pt;">
</p>
<p dir="ltr" style="margin-bottom:0.0001pt;">
<em><span style="font-family:courier new;">>>Also, try fixing all the reuse variables to 0 and solving the MIP. If it is infeasible, you immediately can add the cut that the sum of the reuse variables is >= 1. </span></em>
</p>
<p dir="ltr" style="margin-bottom:0.0001pt;">
<span style="font-family:courier new;">I added then constraint sum a(i)>=1, and the bound is stuck at 1 (log_smallK_o3_v2).</span>
</p>
<p dir="ltr" style="margin-bottom:0.0001pt;">
<span style="font-family:courier new;">Similarly no move if I use obj 2. The bound shows 0, even though I know that for this particular graph there would be 28 repeated colors and if those are applied to the nodes with the lowest weights within groups the objective should be at least 2.5518. </span><span style="font-family: 'courier new';">I really don't understand this behavior.</span>
</p>
<p dir="ltr" style="margin-bottom:0.0001pt;">
</p>
<p dir="ltr" style="margin-bottom:0.0001pt;">
<em><span style="font-family:courier new;">>>Regarding models with the first objective, try setting CPLEX's clique cut parameter to its most aggressive setting of 3. That might help performance.</span></em>
</p>
<p dir="ltr" style="margin-bottom:0.0001pt;">
<span style="font-family: 'courier new';">I tried that, as well as all other aggressive cuts, the bound doesn't move.</span>
</p>
<p dir="ltr" style="margin-bottom:0.0001pt;">
</p>
<p dir="ltr" style="margin-bottom:0.0001pt;">
<em><span style="font-family:courier new;">>>Also, you could run CPLEX's conflict refiner if the model is infeasible, and the resulting conflict may shed light on some tighter cuts.</span></em>
</p>
<p dir="ltr" style="margin-bottom:0.0001pt;">
<span style="font-family:courier new;">Can you give me some more hints on how to use the conflict refiner efficiently?</span>
</p>
none, view_forum, view_categoryurn:lsid:ibm.com:forum:8f348775-2506-4dd1-8eb6-bc7221f32364Re: No proof of optimality2013-08-06T21:04:52.668ZEdKlotz270002TE51active2013-08-06T21:04:52.668Z
<p dir="ltr">
After looking at the model description, I am a bit puzzled as to how the best node value could be 0 in the log you sent, even at the root node. The simplest representation of the vertex coloring model would consist of minimizing the sum of the w variables, subject to the diffNeighColor and oneColor constraints. If I just look at that objective and those two groups of constraints, I believe they already imply a positive objective at the root node relaxation.
</p>
<p dir="ltr">
Specifically, let's follow on Daniel's point that vertices in a clique require different colors. So, suppose I consider a graph consisting of 3 vertices with edges connecting each pair. If we create this minimal vertex coloring formulation involving just the diffNeighColor and oneColor constraints, we can add up all of the constraints and show that the sum of the w variables is at least 2. This does not make use of the integrality of the variables at all, so it applies to the LP relaxation as well as the MIP. This holds regardless of the number of colors available. It also holds regardless of the specific edge set of the graph; as soon as you have a single edge in the graph, the LP relaxation objective must be at least 2.
</p>
<p dir="ltr">
So, how did the node log you attached have a zero objective, not only for the root, but for many subsequent nodes in the optimization? Were you using your second objective? If so, can you post a log for a challenging model for the first objective? I'm not completely clear on the second objective; is it trying to minimize the sum of reused colors in a group that allows violations of the basic unique color requirement for edges?
</p>
<p dir="ltr">
If I correctly understand your second objective, I am not particularly surprised that the model with the second objective is more difficult to solve for a branch and cut solver like CPLEX than the first. You are introducing some soft constraints with the second objective. Soft constraints can weaken a formulation in the sense that certain infeasibilities that previously could be used to derive cuts no longer are available. Think about it this way; if you had a knapsack constraint, you initially might be able to deduce numerous cover cuts. But, if you soften it by subtracting a surplus variable, you remove those cover cuts. The same thing applies for your model with clique cuts.
</p>
<p dir="ltr">
So, are most of your performance difficulties occurring with the second objective, or do you have them with the first objective as well? I'd really like to see a node log from a problematic run using the first objective, as I now have concluded the log you sent above involves the second objective, not the first.
</p>
<p dir="ltr">
Regarding models with the first objective, try setting CPLEX's clique cut parameter to its most aggressive setting of 3. That might help performance.
</p>
<p dir="ltr">
Regarding models with the second objective, try solving an auxiliary model where you minimize just the sum of the reuse variables. Also, try fixing all the reuse variables to 0 and solving the MIP. If it is infeasible, you immediately can add the cut that the sum of the reuse variables is >= 1. Also, you could run CPLEX's conflict refiner if the model is infeasible, and the resulting conflict may shed light on some tighter cuts.
</p>
<p dir="ltr">
</p>
none, view_forum, view_categoryurn:lsid:ibm.com:forum:c140e07f-fb18-461a-a985-43ac40da7878Re: No proof of optimality2013-08-03T13:22:35.374ZDanielJunglas270002S4SXactive2013-08-03T13:22:35.374Z
<p dir="ltr">
Some comments that came to my mind concerning the second case (minimize number of vertices in a group that get the same color):
</p>
<ol dir="ltr">
<li>
diffNeighColor_validineq is redundant, isn't it? It is implied by diffNeighColor.
</li>
<li>
groupReuse2 and groupReuse3 also look redundant. If VertexWeight[i]>0 then a[i] will only be >0 in an optimal solution if b[i][j][k]>0 and that will only be >0 if a[i][k]>0 and a[j][k]>0 (otherwise the solution is not optimal). If VertexWeight[i]==0 then the value of a[i] does not matter anyway.
</li>
<li>
I think in the second case you can do better than constraint maxColors: Since there is no difference between colors you can just set w[0..NbColors-]=1 and w[0..Colors]=0. This will allow CPLEX presolve to eliminate the w variables from your model. Not sure if CPLEX would always pick up this reduction otherwise.
</li>
<li>
Not sure if this will help but I think the following is a valid inequality: Assume G is a group and i is a vertex in that group. If i is colored k then a[i] must be one if at least one other vertex in G is colored k. So for each color k we have (|G|-1)*a[i] >= sum(j in G && j != i) x[j][k] - (|G|-1)*(1 - x[i][k]).<br />
You could look for other combinatorial properties like this that give rise to valid inequalities.
</li>
</ol>
<p dir="ltr">
Vertex coloring using branch&bound/cut is a well studied problem (see for example <a href="http://www.optimization-online.org/DB_FILE/2003/09/715.pdf">this paper</a>). There are some valid inequalities/facets that are not too hard to find. You could try adding some of them to your formulation.
</p>
none, view_forum, view_categoryurn:lsid:ibm.com:forum:dda93f32-aded-43b7-8e79-e1e64daf72ecRe: No proof of optimality2013-08-02T14:59:42.759Zazak 270004FD3Nactive2013-08-02T14:59:42.759Z2013-09-24T15:13:01.581Zazak 270004FD3Nactive
<div dir="ltr">
Thank you for the comments. Replying to your questions, the problem is a vertex coloring problem, where the vertices have certain weights <0;1> (some of them may have 0 indeed, I have tens of these graphs to analyze). Within the graph, there is also a number of vertex groups (vertices within a group are not always connected, so it's not a clique) and the colors should not be reused within a group. There are two problems that I look at:<br />
</div>
<div dir="ltr">
1) In the first approach the objective is to find chromatic number X with the grouping constraints, this is solved easily.
</div>
<div dir="ltr">
2) The upper bound on the number of available colors is lower than X found in 1) and the objective is to minimize the sum of weights of those vertices that are colored with the same color in a group.
</div>
<div dir="ltr">
</div>
<div dir="ltr">
I also enclose the model below (you're right Daniel, I dropped C2 from the previous post). I use CPLEX 12.5, tried the settings suggested by Ed and as he suspected, it didn't help.
</div>
<div dir="ltr">
</div>
<div dir="ltr">
-------------------------------------------------
</div>
<div dir="ltr">
</div>
<div dir="ltr">
</div>
<div dir="ltr">
-------------------------------------------------
</div>
<div dir="ltr">
</div>
<div dir="ltr">
I can try tightening the bound by adding the following valid inequality:
</div>
<div dir="ltr">
</div>
<div dir="ltr">
forall (i in Vertices, g in Grouping: GroupSize>NbColors, k in Colors)
</div>
<div dir="ltr">
groupReuse_validineq:
</div>
<div dir="ltr">
sum(i in Vertices)a[i]*(VertexWeight[i])>= sum (g) of (GroupSize-NbColors) lowest VertexWeight
</div>
<div dir="ltr">
</div>
<div dir="ltr">
but there is still a chance, the sum on the right side is 0.
</div>
none, view_forum, view_categoryurn:lsid:ibm.com:forum:9d2dd47a-2cdf-4f21-8ada-f3c6b0676ab4Re: No proof of optimality2013-08-02T14:44:32.859Zazak 270004FD3Nactive2013-08-02T14:44:32.859Z2013-09-24T15:12:33.588Zazak 270004FD3Nactive
<div dir="ltr">
Thank you for the comments. Replying to your questions, the problem is a vertex coloring problem, where the vertices have certain weights <0;1> (some of them may have 0 indeed, I have tens of these graphs to analyze). Within the graph, there is also a number of vertex groups (vertices within a group are not always connected, so it's not a clique) and the colors should not be reused within a group. There are two problems that I look at:<br />
</div>
<div dir="ltr">
1) In the first approach the objective is to find chromatic number X with the grouping constraints, this is solved easily.
</div>
<div dir="ltr">
2) The upper bound on the number of available colors is lower than X found in 1) and the objective is to minimize the sum of weights of those vertices that are colored with the same color in a group.
</div>
<div dir="ltr">
</div>
<div dir="ltr">
I also enclose the model below (you're right Daniel, I dropped C2 from the previous post). I use CPLEX 12.5, tried the settings suggested by Ed and as he suspected, it didn't help.
</div>
<div dir="ltr">
</div>
<div dir="ltr">
-------------------------------------------------
</div>
<div dir="ltr">
</div>
<div dir="ltr">
</div>
<div dir="ltr">
-------------------------------------------------
</div>
<div dir="ltr">
</div>
<div dir="ltr">
I can try tightening the bound by adding the following valid inequality:
</div>
<div dir="ltr">
</div>
<div dir="ltr">
forall (i in Vertices, g in Grouping: GroupSize>NbColors, k in Colors)
</div>
<div dir="ltr">
groupReuse_validineq:
</div>
<div dir="ltr">
sum(i in Vertices)a[i]*(VertexWeight[i])>= sum (g) of (GroupSize-NbColors) lowest VertexWeight
</div>
<div dir="ltr">
</div>
<div dir="ltr">
but there is still a chance, the sum on the right side is 0.
</div>
none, view_forum, view_categoryurn:lsid:ibm.com:forum:c70bcdc8-a27b-40c0-9788-e2326231c398Re: No proof of optimality2013-08-02T01:30:14.715ZEdKlotz270002TE51active2013-08-02T01:30:14.715Z
<p dir="ltr">
And one other thing. Try to provide a reasonable upper bound on the variables associated with the assignment of the color to the vertex. For example, if you use different integer values to identify different colors, and your graph has 150 vertices, then a bound of 150 is available for these variables since the worst you can do is assign a distinct color to each vertex. While this is obvious on the context of the graph theory problem, I doubt it is so clear to to CPLEX based on the equations in the model you provide. Such bounds could help tighten the formulation, which in turn will yield more progress in the dual bound.
</p>
none, view_forum, view_category