Originally posted by: excalibur1491

Hello,

 

I am very new to CPLEX and I am writing my first model for a MIP problem. I am using a lot of indicator constraints and CPLEX seems to struggle to solve the problems quickly for more than 500 variables.

The description of the problem is as follows:

You are given a  grid (graph) where the weight of edges is unknown. For each edge ei,  there are two possibles weights eiA or eiB (which are known as part of the data).

Then there is a matrix (the weighted Laplacian matrix L ¹ ) that contains all these weight variables and is multiplied by a vector of variables v0,v1,...,vn  like this L v = R, where R is a vector containing all 0's and a single 1.

As you can see, this is not linear because I am multiplying weight variables (in L) with other variables (of v).

So the way I have done this is by writing the equations resulting from the multiplication of L and v with some fake variables i_x_y. And so I have a bunch of linear equations like this:

i_1_2 + i_2_3 - i_3_4 - i_4_5 = 1

i_3_4 + i_5_7 - i_8_10 - i_8_9 = 0

i_2_3 - i_4_5 - i_7_6 = 0

......

 

And then a lot of indicator constraints as follows:

b1 = 1 -> i_1_2 - e1A * v0 =0   \ You chose weight A for edge e2

b1 = 0 -> i_1_2 - e1B *v0 = 0  \ You chose weight B for edge e1

b2 = 1 -> i_3_4 ...

b2 = 0 -> i_3_4 ....

.....

 

Therefore I have 2*number-of-edges indicator constraints (which may be a lot ?) and number_of_nodes linear equations (of at most 8 terms each, because its a grid graph). The indicator constraints bind the terms of the equations to the v variables.

 

Then there is a budget constraint that limits the number of boolean variables that can be true.

The objective is to minimize the value of one (yes, just one) of the variables in v (the one that is in the same row as the value 1 in the vector R previously described).

 

All my variables are free (or Binary). I should try to find bounds that can help CPLEX, but I haven't been able to yet. But in any case, there is no bound restriction on any of those variables.

 

It seems to be ok with small instances, but grids of size 10x10 create 636 columns (which I didn't think was too much) and CPLEX takes ~40s to solve it, but for 15x15 grids (~1400 vars) it takes a good 700s... Is my modelling choice wrong? I don't see any otehr way to do it without indicator constraints. Scalability is very important, I would like to solve grids of at least 30x30 (at the very least..)

 

--

¹ The weighted Laplacian is defined as:

Lij = - weight_edge_i_to_j , if i != j

Lij = sum of weights of edges touching i , if i == j

Lij = 0 otherwise 

--

 

Also, I should add that the log of CPLEx shows several times the word "unbounded" in the "Objective" column, which worries me. Should it actually worry me?

        Nodes                                         Cuts/
   Node  Left     Objective  IInf  Best Integer    Best Bound    ItCnt     Gap

      0     0     unbounded                                          0         
      0     2     unbounded                                          0         
Elapsed real time =   0.02 sec. (tree size =  0.01 MB, solutions = 0)
*     3     3      integral     0        1.8977                    838     --- 
     29     7        cutoff              1.8977                  11690     --- 
     49     7        cutoff              1.8977                  22934     --- 
     69     7        cutoff              1.8977                  31030     --- 
     89     7        cutoff              1.8977                  39568     --- 
    109     7        cutoff              1.8977                  50505     --- 
    129     7        cutoff              1.8977                  58858     --- 
    149     7        cutoff              1.8977                  67750     --- 
    169     7        cutoff              1.8977                  76011     --- 
    261     7        cutoff              1.8977                 110321     --- 
Elapsed real time =   7.48 sec. (tree size =  0.01 MB, solutions = 0)
    357     7        cutoff              1.8977                 144265     --- 
    453     7        cutoff              1.8977                 176141     --- 
    565     7        cutoff              1.8977                 209336     --- 
    681     7        cutoff              1.8977                 240631     --- 
    813     7        cutoff              1.8977                 272101     --- 
    961     7        cutoff              1.8977                 302109     --- 
   1133     7        cutoff              1.8977                 330179     --- 
   1341     7        cutoff              1.8977                 354329     --- 
   1643     7     unbounded              1.8977                 369748     --- 
   1770     4        cutoff              1.8977                 406808     --- 

 

 

 

I didn't want to fill my post with code, but as an example, here is a small model (4x4 grid, in this example all the edges take weight 1 or 0.01):
 

Minimize
obj: v0
Subject To


l0: i_1_0 + i_2_0 - i_1_1 - i_2_3 = 1
l1: - i_1_0 + i_1_1 + i_3_1 + i_4_1 - i_3_2 - i_4_4 = 0
l2: - i_3_1 + i_3_2 + i_5_2 - i_5_5 = 0
l3: - i_2_0 + i_2_3 + i_6_3 + i_7_3 - i_6_4 - i_7_6 = 0
l4: - i_4_1 - i_6_3 + i_4_4 + i_6_4 + i_8_4 + i_9_4 - i_8_5 - i_9_7 = 0
l5: - i_5_2 - i_8_4 + i_5_5 + i_8_5 + i_10_5 = 0
l6: - i_7_3 + i_7_6 + i_11_6 - i_11_7 = 0
l7: - i_9_4 - i_11_6 + i_9_7 + i_11_7 + i_12_7 = 0

c0: b_1 = 1 -> i_1_0 - 1 v0 = 0
c1: b_1 = 0 -> i_1_0 - 0.01 v0 = 0
c2: b_2 = 1 -> i_2_0 - 1 v0 = 0
c3: b_2 = 0 -> i_2_0 - 0.01 v0 = 0
c4: b_1 = 1 -> i_1_1 - 1 v1 = 0
c5: b_1 = 0 -> i_1_1 - 0.01 v1 = 0
c6: b_2 = 1 -> i_2_3 - 1 v3 = 0
c7: b_2 = 0 -> i_2_3 - 0.01 v3 = 0
c8: b_3 = 1 -> i_3_1 - 1 v1 = 0
c9: b_3 = 0 -> i_3_1 - 0.01 v1 = 0
c10: b_4 = 1 -> i_4_1 - 1 v1 = 0
c11: b_4 = 0 -> i_4_1 - 0.01 v1 = 0
c12: b_3 = 1 -> i_3_2 - 1 v2 = 0
c13: b_3 = 0 -> i_3_2 - 0.01 v2 = 0
c14: b_4 = 1 -> i_4_4 - 1 v4 = 0
c15: b_4 = 0 -> i_4_4 - 0.01 v4 = 0
c16: b_5 = 1 -> i_5_2 - 1 v2 = 0
c17: b_5 = 0 -> i_5_2 - 0.01 v2 = 0
c18: b_5 = 1 -> i_5_5 - 1 v5 = 0
c19: b_5 = 0 -> i_5_5 - 0.01 v5 = 0
c20: b_6 = 1 -> i_6_3 - 1 v3 = 0
c21: b_6 = 0 -> i_6_3 - 0.01 v3 = 0
c22: b_7 = 1 -> i_7_3 - 1 v3 = 0
c23: b_7 = 0 -> i_7_3 - 0.01 v3 = 0
c24: b_6 = 1 -> i_6_4 - 1 v4 = 0
c25: b_6 = 0 -> i_6_4 - 0.01 v4 = 0
c26: b_7 = 1 -> i_7_6 - 1 v6 = 0
c27: b_7 = 0 -> i_7_6 - 0.01 v6 = 0
c28: b_8 = 1 -> i_8_4 - 1 v4 = 0
c29: b_8 = 0 -> i_8_4 - 0.01 v4 = 0
c30: b_9 = 1 -> i_9_4 - 1 v4 = 0
c31: b_9 = 0 -> i_9_4 - 0.01 v4 = 0
c32: b_8 = 1 -> i_8_5 - 1 v5 = 0
c33: b_8 = 0 -> i_8_5 - 0.01 v5 = 0
c34: b_9 = 1 -> i_9_7 - 1 v7 = 0
c35: b_9 = 0 -> i_9_7 - 0.01 v7 = 0
c36: b_10 = 1 -> i_10_5 - 1 v5 = 0
c37: b_10 = 0 -> i_10_5 - 0.01 v5 = 0
c38: b_11 = 1 -> i_11_6 - 1 v6 = 0
c39: b_11 = 0 -> i_11_6 - 0.01 v6 = 0
c40: b_11 = 1 -> i_11_7 - 1 v7 = 0
c41: b_11 = 0 -> i_11_7 - 0.01 v7 = 0
c42: b_12 = 1 -> i_12_7 - 1 v7 = 0
c43: b_12 = 0 -> i_12_7 - 0.01 v7 = 0

budget: 1 b_10 + 1 b_11 + 1 b_8 + 1 b_9 + 1 b_12 + 1 b_1 + 1 b_2 + 1 b_3 + 1 b_4 + 1 b_5
 + 1 b_6 + 1 b_7 <= 2

Bounds

    v0 free
    v1 free
    v2 free
    v3 free
    v4 free
    v5 free
    v6 free
    v7 free

i_6_4 free
i_6_3 free
i_5_2 free
i_5_5 free
i_9_4 free
i_9_7 free
i_7_6 free
i_8_4 free
i_8_5 free
i_7_3 free
i_12_7 free
i_1_1 free
i_1_0 free
i_3_2 free
i_3_1 free
i_11_7 free
i_11_6 free
i_2_3 free
i_2_0 free
i_10_5 free
i_4_1 free
i_4_4 free

Binaries
b_10
b_11
b_8
b_9
b_12
b_1
b_2
b_3
b_4
b_5
b_6
b_7

 

 

Thanks for your ideas

#CPLEXOptimizers
#DecisionOptimization

The expansion of Lv = R contains a mix of additions and subtractions. Why are the terms not all be added?
 

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: excalibur1491

Hi,

 

In the Laplacian matrix, Lij = - weight_edge(i,j) if i != j, so apart from the diagonal of the matrix, they are all negative.

The non-diagonal values in that matrix are the eiA or eiB (of my original post), and in the example: 

c4: b_1 = 1 -> i_1_1 - 1 v1 = 0
c5: b_1 = 0 -> i_1_1 - 0.01 v1 = 0

 

Since those are always positive numbers, the Lij (where i!=j) elements of the Laplacian are always negative, thus the substractions. I suppose I could have let them be additions, and then in the indicator constraints write:

c4: b_1 = 1 -> i_1_1 - 1 v1 = 0
c5: b_1 = 0 -> i_1_1 - 0.01 v1 = 0

 

But it should be the same I believe.

 

Thanks for your reply.

#CPLEXOptimizers
#DecisionOptimization

There's nothing wrong with the subtraction; I just wanted to make sure they weren't typos.

I'm not sure it will make a difference (let alone should make a difference), but if you can assert a priori bounds on the v variables, you might try replacing the indicator constraints with "big M" constraints. With indicators, CPLEX tries to infer such bounds, but may be having problems in this case.

Let's assume that L_y <= v_y <= U_y for each y, with L and U constants. You can define i_x_y with the following four inequalities:

i_x_y <= e_xA v_y + M1 (1 - b_x)

i_x_y <= e_xB v_y + M2 b_x

i_x_y >= e_xA v_y - M2 (1 - b_x)

i_x_y >= e_xB v_y - M1 b_x

with

M1 = max( (e_xB - e_xA) L_y, (e_xB - e_xA) U_y )

M2 = max( (e_xA - e_xB) L_y, (e_xA - e_xB) U_y ).

(It wouldn't hurt if you checked my algebra there.)

The tighter L and U are (while being valid bounds for v), the better CPLEX's performance will be.

 

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: BoJensen

Posting on behalf of Ed Klotz, who currently has connection issues :

 

First of all, am I correct that the linear constraints in this model
involve the conservation of flow requirements for your graph?

Second, regarding the declarations of unboundedness, this seems possible
given the free variables in your model.   Given that you are minimizing
v0, do you believe there are any conditions in the model that would prevent
the model from being unbounded if some or all of the indicator constraints
were removed (which is exactly what CPLEX does for the LP relaxation)?
One thing you could do is put a finite lower bound on v0, e.g.
v0 >= -10000, then see if the initial root node relaxation is unbounded
like it was in the log you attached.   Keep in mind here that CPLEX relaxes
indicator constraints by removing them completely.   Thus, when CPLEX relaxes
the indicator constraint on v0, I don't think there are any constraints
in the model that prevent v0 from moving to -infinity.

Third, your point about finding bounds on the variables is important.
If you can do that, I suspect you will see better performance.   Just
as a test, try putting bounds of say [-1000,1000] on the free variables
and see how this affects performance.    If those version of the model solve
quickly, at least you have a heuristic for finding starting feasible solutions
for the model with infinite upper and lower bound.

And finally, there is an alternative way to formulate this, but it relies
on the presence of finite bounds on continuous variables.   Your model
involves products of a continuous variable and a binary variable.   This
can be modelled using linearization techniques where you introduce a new
variable and some linear constraints that ensure that the new variable
always equals the product of the binary and continuous variables associated
with it in the linearization constraints.    See
http://www.leandro-coelho.com/linearization-product-variables/ for how to
do this, including when the continuous variable is free.  As you will see,
this method is predicated on the presence of finite bounds on the continuous
variable.  I would expect the linearization approach to work better than the
indicator approach if you could derive modest finite bounds.   But if you can
only derive large bounds, nor none at all, the indicator formulation that
you currently have should work better.  I think the bounds, if any, that can
be derived, depend specifically on the values in your matrix L; for some
instances of L you may be able to derive bounds, whereas for others you
may not.

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: excalibur1491

Hi,

 

Thanks every one for your help!

So, clearly the bounds are a problem. I have found a way of getting bounds for all my variables:

The "b" booleans are "investment decisions", so I first solve the problem with full investment (no budget limit, so all the b's are 1), that gives me an upper bound on the v variables.  I do the same with a budget of 0 (meaning I can't invest and all the b's are 0), that gives me a lower bound for all the v variables. From those bounds I then deduce the bounds of the i_x_y variables. The bounds are kind-of tight, but it's going to be dependent on my input. For the instances I am trying the domains are around [0,100] for most variables, and I think in practice the data I will be getting is not going to differ much from this "mock" data I have.

This improved the solving time a lot, from 30s to 1s and from 700s to 200s. But I am still far from being able to scale to the sizes I want.

 

@PaulRubin fdff265a-3b6c-4b56-a592-3793926aaf7a, Thanks for your reply. My understanding is that indicator constraints are then somewhat converted into big-M notation where the M is chosen "smartly" ​: indicator constraints enables CPLEX® either to branch explicitly on the indicator constraint, or to use MIP preprocessing to derive a tighter value of Big M that makes the formulation more stable. I will give it a try though, I am in no rush and I'd rather do this properly, so I am open to try all options. :)

@EdKlotz 76679752-a695-4301-a8a6-a46603aab7bb​, @BoJensen 122a4656-de6d-45f0-a321-4afff9b8db5f​ Thanks for your answer, it was quite enlightening!

First, the linear constraints do not involve flow conservations (as far as I can tell). The problem is about finding the value of effective resistance in an electrical network. I know that in electric networks the flow is conserved, but with this formulation that I was given, I am not sure those values actually represent intensity flow. This Laplacian-matrix trick is derived from the eigenvalues of the Laplacian, which somehow magically gives you the effective resistance between two pairs of nodes.  But I have no reason to believe that it is linked to intensities in the network actually... the knowledge I have about this is a bit "fuzzy" (and so is the case for the people that asked me to work on this actually...)

Second & third, as I said above in this post, I fixed my unbounded issues. CPLEX does not report "unbounded" anymore! :)

Fourth: This is very interesting actually. I will try this thing right away, now that I bounded all my variables.
Now, I do have a question about this: in the last four equations (which are the ones I am looking at), the  fourth equation seems to be redundant with the right hand side of the third. Am I seeing this wrong?

What I want to try is the following:

-for each i_x_y I have in the linear equations, it will be substituted by  eiA*i_x_y + eiB * i_x_y'  . Where i_x_y = vx*by and i_x_y' = vx*(1-by) . This should be equivalent to what I had with my indicator constraints, right?
-for each i_x_y and i_x_y', give the four equations from the link you gave me. That will force either i_x_y or i_x_y' to take the value vx and the other will have to take the value 0.

Did I understand the linearisation correctly? The fourth equation is the only thing that I don't understand.

 

I will post once I have implemented this.

 

Thanks for your help!
 

 

 

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: EdKlotz

I had a look at the link and agree that the 4th and final constraint appears to be unnecessary both when x = 0 and x = 1.  In fact,

I just found another link, http://yetanothermathprogrammingconsultant.blogspot.com/2008/05/multiplication-of-continuous-and-binary.html, 

that appears to confirm you only need the first 3 constraints.  But, just to be sure, try creating a simple model with this linearization where you

minimize and maximize the z variable subject to just the first 3 linearization constraints.    If it is truly redundant, the z variable will still be zero

or A.   If it is needed, at least one of those two runs should result in a nonzero value for z.

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: excalibur1491

Hi, so I have tried the linearization and it gives the same results, as expected, but seems to take longer.

 

First, the bounds that I had earlier were actually wrong. So when I said that they got me from 30s to 1s, it's actually from 30s to 14s using the indicator constraints.

 

Using this correct bounds, I implemented the linearization (the lower bound is always 0).

 

For each i_x_y that I had, I broke it like this:  eiA*vi*bi + eiB*vi*(1-b) = (eiA - eiB)*vi*b + eiB*vi = (eiA - eiB)*i_x_y + eiB*vi   . I kept the same names, but i_x_y is now clearly a different thing than what it was with the indicator constraints.

And for each i_x_y I have the equations from the link.

As an example, for a 3x3 grid, I have a lp like this:

Minimize
obj: v0
Subject To

l0: 0.99 i_1_0 + 0.01 v0 + 0.99 i_2_0 + 0.01 v0 - 0.99 i_1_1 - 0.01 v1  - 0.99 i_2_3 - 0.01 v3  = 1
l1: - 0.99 i_1_0 - 0.01 v0  + 0.99 i_1_1 + 0.01 v1 + 0.99 i_3_1 + 0.01 v1 + 0.99 i_4_1 + 0.01 v1 - 0.99 i_3_2 - 0.01 v2  - 0.99 i_4_4 - 0.01 v4  = 0
l2: - 0.99 i_3_1 - 0.01 v1  + 0.99 i_3_2 + 0.01 v2 + 0.99 i_5_2 + 0.01 v2 - 0.99 i_5_5 - 0.01 v5  = 0
l3: - 0.99 i_2_0 - 0.01 v0  + 0.99 i_2_3 + 0.01 v3 + 0.99 i_6_3 + 0.01 v3 + 0.99 i_7_3 + 0.01 v3 - 0.99 i_6_4 - 0.01 v4  - 0.99 i_7_6 - 0.01 v6  = 0
l4: - 0.99 i_4_1 - 0.01 v1  - 0.99 i_6_3 - 0.01 v3  + 0.99 i_4_4 + 0.01 v4 + 0.99 i_6_4 + 0.01 v4 + 0.99 i_8_4 + 0.01 v4 + 0.99 i_9_4 + 0.01 v4 - 0.99 i_8_5 - 0.01 v5  = 0
l5: - 0.99 i_5_2 - 0.01 v2  - 0.99 i_8_4 - 0.01 v4  + 0.99 i_5_5 + 0.01 v5 + 0.99 i_8_5 + 0.01 v5 + 0.99 i_10_5 + 0.01 v5 - 0.99 i_10_8 - 0.01 v8  = 0
l6: - 0.99 i_7_3 - 0.01 v3  + 0.99 i_7_6 + 0.01 v6 + 0.99 i_11_6 + 0.01 v6 = 0
l8: - 0.99 i_10_5 - 0.01 v5  + 0.99 i_10_8 + 0.01 v8 + 0.99 i_12_8 + 0.01 v8 = 0

lin1l0: i_1_0 >= 0.0
lin1l1: i_2_0 >= 0.0
lin1l2: i_1_1 >= 0.0
lin1l3: i_2_3 >= 0.0
lin1l4: i_3_1 >= 0.0
lin1l5: i_4_1 >= 0.0
lin1l6: i_3_2 >= 0.0
lin1l7: i_4_4 >= 0.0
lin1l8: i_5_2 >= 0.0
lin1l9: i_5_5 >= 0.0
lin1l10: i_6_3 >= 0.0
lin1l11: i_7_3 >= 0.0
lin1l12: i_6_4 >= 0.0
lin1l13: i_7_6 >= 0.0
lin1l14: i_8_4 >= 0.0
lin1l15: i_9_4 >= 0.0
lin1l16: i_8_5 >= 0.0
lin1l17: i_10_5 >= 0.0
lin1l18: i_10_8 >= 0.0
lin1l19: i_11_6 >= 0.0
lin1l20: i_12_8 >= 0.0



lin2r0: i_1_0 - 115.0001 b_1 <= 0
lin2r1: i_2_0 - 115.0001 b_2 <= 0
lin2r2: i_1_1 - 115.0001 b_1 <= 0
lin2r3: i_2_3 - 115.0001 b_2 <= 0
lin2r4: i_3_1 - 115.0001 b_3 <= 0
lin2r5: i_4_1 - 115.0001 b_4 <= 0
lin2r6: i_3_2 - 115.0001 b_3 <= 0
lin2r7: i_4_4 - 115.0001 b_4 <= 0
lin2r8: i_5_2 - 115.0001 b_5 <= 0
lin2r9: i_5_5 - 115.0001 b_5 <= 0
lin2r10: i_6_3 - 115.0001 b_6 <= 0
lin2r11: i_7_3 - 115.0001 b_7 <= 0
lin2r12: i_6_4 - 115.0001 b_6 <= 0
lin2r13: i_7_6 - 115.0001 b_7 <= 0
lin2r14: i_8_4 - 115.0001 b_8 <= 0
lin2r15: i_9_4 - 115.0001 b_9 <= 0
lin2r16: i_8_5 - 115.0001 b_8 <= 0
lin2r17: i_10_5 - 115.0001 b_10 <= 0
lin2r18: i_10_8 - 115.0001 b_10 <= 0
lin2r19: i_11_6 - 115.0001 b_11 <= 0
lin2r20: i_12_8 - 115.0001 b_12 <= 0

lin3l0: v0 + 115.0001 b_1 - i_1_0 <= 115.0001
lin3l1: v0 + 115.0001 b_2 - i_2_0 <= 115.0001
lin3l2: v1 + 115.0001 b_1 - i_1_1 <= 115.0001
lin3l3: v3 + 115.0001 b_2 - i_2_3 <= 115.0001
lin3l4: v1 + 115.0001 b_3 - i_3_1 <= 115.0001
lin3l5: v1 + 115.0001 b_4 - i_4_1 <= 115.0001
lin3l6: v2 + 115.0001 b_3 - i_3_2 <= 115.0001
lin3l7: v4 + 115.0001 b_4 - i_4_4 <= 115.0001
lin3l8: v2 + 115.0001 b_5 - i_5_2 <= 115.0001
lin3l9: v5 + 115.0001 b_5 - i_5_5 <= 115.0001
lin3l10: v3 + 115.0001 b_6 - i_6_3 <= 115.0001
lin3l11: v3 + 115.0001 b_7 - i_7_3 <= 115.0001
lin3l12: v4 + 115.0001 b_6 - i_6_4 <= 115.0001
lin3l13: v6 + 115.0001 b_7 - i_7_6 <= 115.0001
lin3l14: v4 + 115.0001 b_8 - i_8_4 <= 115.0001
lin3l15: v4 + 115.0001 b_9 - i_9_4 <= 115.0001
lin3l16: v5 + 115.0001 b_8 - i_8_5 <= 115.0001
lin3l17: v5 + 115.0001 b_10 - i_10_5 <= 115.0001
lin3l18: v8 + 115.0001 b_10 - i_10_8 <= 115.0001
lin3l19: v6 + 115.0001 b_11 - i_11_6 <= 115.0001
lin3l20: v8 + 115.0001 b_12 - i_12_8 <= 115.0001

lin3r0: i_1_0 - v0 <= 0
lin3r1: i_2_0 - v0 <= 0
lin3r2: i_1_1 - v1 <= 0
lin3r3: i_2_3 - v3 <= 0
lin3r4: i_3_1 - v1 <= 0
lin3r5: i_4_1 - v1 <= 0
lin3r6: i_3_2 - v2 <= 0
lin3r7: i_4_4 - v4 <= 0
lin3r8: i_5_2 - v2 <= 0
lin3r9: i_5_5 - v5 <= 0
lin3r10: i_6_3 - v3 <= 0
lin3r11: i_7_3 - v3 <= 0
lin3r12: i_6_4 - v4 <= 0
lin3r13: i_7_6 - v6 <= 0
lin3r14: i_8_4 - v4 <= 0
lin3r15: i_9_4 - v4 <= 0
lin3r16: i_8_5 - v5 <= 0
lin3r17: i_10_5 - v5 <= 0
lin3r18: i_10_8 - v8 <= 0
lin3r19: i_11_6 - v6 <= 0
lin3r20: i_12_8 - v8 <= 0


budget: 1 b_10 + 1 b_11 + 1 b_8 + 1 b_9 + 1 b_12 + 1 b_1 + 1 b_2 + 1 b_3 + 1 b_4 + 1 b_5
 + 1 b_6 + 1 b_7 <= 2

Bounds

0 <= v0 <= 115.1
0 <= v1 <= 115.1
0 <= v2 <= 115.1
0 <= v3 <= 115.1
0 <= v4 <= 115.1
0 <= v5 <= 115.1
0 <= v6 <= 115.1
0 <= v8 <= 115.1


Binaries
b_10
b_11
b_8
b_9
b_12
b_1
b_2
b_3
b_4
b_5
b_6
b_7

 

 

I tried to solve a 10x10 grid graph, that the indicators model was able to solve in 14s. It takes me 46s with the linearization.

At the beginning, CPLEX says the following:

 

Number of columns 636
Tried aggregator 1 time.
MIP Presolve eliminated 357 rows and 0 columns.
Reduced MIP has 1171 rows, 636 columns, and 3843 nonzeros.
Reduced MIP has 180 binaries, 0 generals, 0 SOSs, and 0 indicators.
Probing fixed 0 vars, tightened 99 bounds.
Probing time =    0.00 sec.
Tried aggregator 1 time.
Presolve time =    0.00 sec.
Probing time =    0.00 sec.
MIP emphasis: balance optimality and feasibility.
MIP search method: traditional branch-and-cut.
Parallel mode: deterministic, using up to 8 threads.
Root relaxation solution time =    0.02 sec.

        Nodes                                         Cuts/
   Node  Left     Objective  IInf  Best Integer    Best Bound    ItCnt     Gap

*     0+    0                          251.6594                    562     --- 
      0     0        0.5025    76      251.6594        0.5025      562   99.80%
      0     0        0.5025    77      251.6594      Cuts: 11      566   99.80%
*     0+    0                          235.4011        0.5025      566   99.79%
      0     0        0.5025    77      235.4011       Cuts: 9      571   99.79%
      0     2        0.5025    77      235.4011        0.5025      571   99.79%
Elapsed real time =   0.51 sec. (tree size =  0.01 MB, solutions = 2)
*     2     2      integral     0      221.4398        0.6025     1249   99.73%
      3     3        0.9951    75      221.4398        0.6025     1252   99.73%
*    10     6      integral     0      213.5604        0.9951     2775   99.53%
     19     5        cutoff            213.5604        0.9951     6130   99.53%
     32     8        cutoff            213.5604        0.9951    12917   99.53%
     47     9        1.9690    74      213.5604        0.9951    17345   99.53%
     68     8       33.9996    94      213.5604        0.9951    24652   99.53%
     89     9        1.9690    91      213.5604        0.9951    33453   99.53%
    120    18       38.2638   107      213.5604        0.9951    43116   99.53%
    219    15        cutoff            213.5604        0.9951    79089   99.53%
Elapsed real time =   3.00 sec. (tree size =  0.01 MB, solutions = 4)
    339     9       51.4965    73      213.5604        0.9951   121885   99.53%
*   373    17      integral     0      208.2519        0.9951   133119   99.52%
    672    13       50.5012   124      208.2519       50.2519   153882   75.87%
    923   187       92.7947    82      208.2519       50.2519   182170   75.87%
   2207  1310        cutoff            208.2519       50.7427   256112   75.63%
   4403  3179        cutoff            208.2519       69.3866   334932   66.68%
   6336  4520        cutoff            208.2519       88.1752   437404   57.66%
   6606  4528      108.3142    98      208.2519       88.1752   515073   57.66%
   8512  6179        cutoff            208.2519       92.7947   583731   55.44%
   9285  6436        cutoff            208.2519       97.4396   680946   53.21%
Elapsed real time =  12.84 sec. (tree size = 51.91 MB, solutions = 5)
   9904  6806      104.3999   100      208.2519       97.4396   793365   53.21%
  10827  7522        cutoff            208.2519      100.1782   852255   51.90%
  11399  7533        cutoff            208.2519      100.2129   982440   51.88%
  11791  7525        cutoff            208.2519      100.2129  1081479   51.88%
  12510  7441        cutoff            208.2519      106.3268  1193687   48.94%
  12907  7222      119.4797    58      208.2519      106.3268  1293904   48.94%
  13390  6911        cutoff            208.2519      107.9745  1391821   48.15%
  13935  6582        cutoff            208.2519      114.3703  1492436   45.08%
  14272  6387      117.4814    89      208.2519      114.3703  1561480   45.08%
  15475  7186        cutoff            208.2519      117.4814  1689480   43.59%
Elapsed real time =  27.85 sec. (tree size = 52.77 MB, solutions = 5)
  16043  7281        cutoff            208.2519      117.4814  1738871   43.59%
  17176  7717      117.4913    54      208.2519      117.4815  1850117   43.59%
  18711  7511        cutoff            208.2519      117.4817  2024196   43.59%
  19295  6948        cutoff            208.2519      117.4817  2106044   43.59%
  20009  6317        cutoff            208.2519      119.4794  2215817   42.63%
  21478  5870        cutoff            208.2519      119.4947  2321240   42.62%
  22365  5429        cutoff            208.2519      119.4947  2375963   42.62%
  23495  4508        cutoff            208.2519      123.1216  2495078   40.88%
  24223  3791        cutoff            208.2519      123.1216  2601125   40.88%
  25338  2737        cutoff            208.2519      133.8520  2687324   35.73%
Elapsed real time =  42.35 sec. (tree size = 21.81 MB, solutions = 5)
  26709  1398        cutoff            208.2519      150.0153  2759705   27.96%

Flow cuts applied:  5
Mixed integer rounding cuts applied:  1

Root node processing (before b&c):
  Real time             =    0.42
Parallel b&c, 8 threads:
  Real time             =   44.34
  Sync time (average)   =    0.02
  Wait time (average)   =    0.00
                          -------
Total (root+branch&cut) =   44.75 sec.

 

With the indicators, the reduced MIP had 1350 columns, so more. But only 814 rows (less than now). Both have the same number of initial columns.

 

The last number on the "nodes" column of the log is 26709 compared to 30650 for the version with indicators. Does this mean there are less decisions made in the b&c algorithm?

How is it possible that linear in-equations are more problematic than indicator constraints to CPLEX?

 

I have MIPEMPHASIS as BALANCED and tried both MIPSEARCH_AUTO and TRADITIONAL. The latter seemed slightly better.

 

Any suggestions on how to improve the model?

 

Thank you!

 

#CPLEXOptimizers
#DecisionOptimization