Presolve: All rows and columns removed, though not optimal

回答済み

Arnaut Goethals

2024年02月23日 12:40 編集済み

• 
• 

   

Dear

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%

関連

• Presolve

0

• 正式なコメント

  

  Simranjit Kaur

  • Gurobi Staff

  2026年11月13日 01:29

  This post is more than two years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum, or try Gurobot, our chatbot interface offering instant, expert-level support.
• 

  Simranjit Kaur

  • Gurobi Staff

  2024年03月19日 03:03

  Please have a look at the articles:

  • What does "Presolve: All rows and columns removed" mean?
  • How do I diagnose a wrong result?

  0

投稿コメントは受け付けていません。