Presolve: All rows and columns removed, though not optimal
AnsweredDear
I am trying to maximize Kendall's W (https://en.wikipedia.org/wiki/Kendall%27s_W) by adding an extra ranking (variable C). I already have an amount of dm rankings, each for alt alternatives. C has the properties that they are all integers from 1 to alt, which is ensured by the constraints using c. The variable ranking gives the sum for each alternative of their given ranking. The average of variable ranking is constant. I try to maximize the sum over all alternatives of the squared difference between ranking and average. However, presolve removes all rows and columns, though it sets C as a decreasing list from alt to 1. Model and output can be seen below. Any help would be very much appreciated!
Thanks in advance! Arnaut
m = gp.Model("qp")
average = (dm+1)*(alt+1)/2
totalRank = [0 for i in range(alt)]
for i in range(alt):
for a in range(dm):
totalRank[i] += X[a][i]
M = alt+2
tuplelistc = []
for i in range(1, alt):
for j in range(i + 1, alt+1):
tuplelistc.append((i , j))
coptions = tuplelist(tuplelistc)
C = m.addVars(list(range(1, alt+1)), vtype=GRB.INTEGER, lb=1, ub = alt, name = "C")
c = m.addVars(coptions, vtype=GRB.BINARY, name = "c")
ranking = m.addVars(list(range(1,alt+1)), vtype=GRB.INTEGER, lb = dm + 1, ub = (dm+1)*alt, name = "ranking")
m.addConstrs(ranking[i] == C[i] + totalRank[i-1] for i in range(1, alt+1))
m.addConstrs(C[i] <= (C[j] - 0.5) + M*c[i,j] for i in range(1, alt) for j in range(i+1, alt+1))
m.addConstrs(C[i] >= (C[j] + 0.5) + M*(1-c[i,j]) for i in range(1, alt) for j in range(i+1, alt+1))
expr = QuadExpr()
for i in range(1, alt+1):
expr.add((ranking[i] - average)*(ranking[i] - average)*12/((dm+1)**2 * ((alt)**3 - (alt))))
m.setObjective(expr, GRB.MAXIMIZE)
m.optimize()
Optimize a model with 8649 rows, 4464 columns and 25854 nonzeros
Model fingerprint: 0x02f111b2
Model has 93 quadratic objective terms
Variable types: 0 continuous, 4464 integer (4278 binary)
Coefficient statistics:
Matrix range [1e+00, 1e+02]
Objective range [2e-04, 2e-04]
QObjective range [6e-07, 6e-07]
Bounds range [1e+00, 7e+02]
RHS range [5e-01, 5e+02]
Presolve removed 8649 rows and 4464 columns
Presolve time: 0.00s
Presolve: All rows and columns removed
Explored 0 nodes (0 simplex iterations) in 0.01 seconds (0.02 work units)
Thread count was 1 (of 16 available processors)
Solution count 1: 0.542754
No other solutions better than 0.542754
Optimal solution found (tolerance 1.00e-04)
Best objective 5.427544656369e-01, best bound 5.427544656369e-01, gap 0.0000%
0
-
Please have a look at the articles:
0
Please sign in to leave a comment.
Comments
1 comment