In [1]:

    

from gurobipy import *


    

In [2]:

    

import random


    

In [3]:

    

#グラフ最適化問題を解く
#グラフ分割問題
#modelの作成関数
def gpp(V,E):
    model =Model("gpp")
    x = {}
    y = {}
    for i in V:
        x[i]  = model.addVar(vtype="B" , name= "in R (%s)" %i)
    for (i,j) in E:
        y[i,j] = model.addVar(vtype= "B" ,name="connection(%s ,%s)" %(i,j))
    model.update()
    model.addConstr(quicksum(x[i] for i in V) == len(V)/2)
    for (i,j) in E:
        model.addConstr(x[i] -x[j] <= y[i,j])
        model.addConstr(x[j] - x[i] <= y[i,j])
    model.setObjective(quicksum(y[i,j] for (i,j) in E))
    model.__data = x
    return model


    

In [4]:

    

#データ作成関数
def make_data(n, prob):
    V = range(1, n+1)
    E = [(i,j) for i in V for j in V if i < j and random.random() < prob]
    return V, E


    

In [5]:

    

if __name__ == "__main__":
    V, E = make_data(30, 0.5)
    model = gpp(V, E)
    model.optimize()
    print "Opt.Val = " , model.ObjVal


    

    




Optimize a model with 403 rows, 231 columns and 1236 nonzeros
Coefficient statistics:
  Matrix range    [1e+00, 1e+00]
  Objective range [1e+00, 1e+00]
  Bounds range    [1e+00, 1e+00]
  RHS range       [2e+01, 2e+01]
Found heuristic solution: objective 99
Presolve time: 0.01s
Presolved: 403 rows, 231 columns, 1236 nonzeros
Variable types: 0 continuous, 231 integer (231 binary)

Root relaxation: objective 0.000000e+00, 72 iterations, 0.01 seconds

    Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

     0     0    0.00000    0   30   99.00000    0.00000   100%     -    0s
H    0     0                      98.0000000    0.00000   100%     -    0s
H    0     0                      93.0000000    0.00000   100%     -    0s
     0     0    0.53571    0   32   93.00000    0.53571  99.4%     -    0s
     0     0    1.04090    0   33   93.00000    1.04090  98.9%     -    0s
     0     0    1.41285    0   35   93.00000    1.41285  98.5%     -    0s
     0     0    1.49548    0   36   93.00000    1.49548  98.4%     -    0s
     0     0    1.59130    0   35   93.00000    1.59130  98.3%     -    0s
     0     0    1.60289    0   36   93.00000    1.60289  98.3%     -    0s
     0     0    1.65468    0   35   93.00000    1.65468  98.2%     -    0s
     0     0    1.66415    0   36   93.00000    1.66415  98.2%     -    0s
     0     0    1.67525    0   34   93.00000    1.67525  98.2%     -    0s
     0     0    1.67525    0   34   93.00000    1.67525  98.2%     -    0s
     0     0    1.67525    0   34   93.00000    1.67525  98.2%     -    0s
     0     2    1.67525    0   34   93.00000    1.67525  98.2%     -    0s
*  207   143              18      92.0000000   21.99111  76.1%  54.1    0s
*  246   164              15      86.0000000   22.00396  74.4%  53.1    0s
*  294   189              14      85.0000000   22.00396  74.1%  50.2    0s
*  313   191              17      84.0000000   26.48769  68.5%  48.8    0s
*  424   221              19      83.0000000   27.55762  66.8%  46.3    0s
*  465   234              16      82.0000000   33.00000  59.8%  45.4    0s
*  469   227              16      81.0000000   33.00000  59.3%  45.2    0s
*  651   286              17      80.0000000   34.34215  57.1%  43.3    1s
* 1253   416              17      79.0000000   43.00000  45.6%  40.9    1s
  4588   577     cutoff   28        79.00000   50.20000  36.5%  38.1    5s
 11047   862     cutoff   27        79.00000   60.68750  23.2%  34.9   10s

Cutting planes:
  Gomory: 3
  Zero half: 3

Explored 18283 nodes (603986 simplex iterations) in 14.09 seconds
Thread count was 2 (of 4 available processors)

Optimal solution found (tolerance 1.00e-04)
Best objective 7.900000000000e+01, best bound 7.900000000000e+01, gap 0.0%
Opt.Val =  79.0

In [6]:

    

#各変数の詳細
for v in model.getVars():
    print v.varname, v.X


    

    




in R (1) 1.0
in R (2) -0.0
in R (3) 1.0
in R (4) 1.0
in R (5) 0.0
in R (6) -0.0
in R (7) 0.0
in R (8) 1.0
in R (9) -0.0
in R (10) 1.0
in R (11) 1.0
in R (12) 1.0
in R (13) 1.0
in R (14) 1.0
in R (15) -0.0
in R (16) 1.0
in R (17) -0.0
in R (18) -0.0
in R (19) 1.0
in R (20) -0.0
in R (21) 0.0
in R (22) 1.0
in R (23) -0.0
in R (24) 0.0
in R (25) 1.0
in R (26) 1.0
in R (27) -0.0
in R (28) 0.0
in R (29) 1.0
in R (30) 0.0
connection(1 ,2) 1.0
connection(1 ,3) 0.0
connection(1 ,4) 0.0
connection(1 ,11) 0.0
connection(1 ,12) 0.0
connection(1 ,13) 0.0
connection(1 ,14) 0.0
connection(1 ,15) 1.0
connection(1 ,16) -0.0
connection(1 ,20) 1.0
connection(1 ,21) 1.0
connection(1 ,22) -0.0
connection(1 ,29) 0.0
connection(2 ,3) 1.0
connection(2 ,5) 0.0
connection(2 ,7) 0.0
connection(2 ,9) 0.0
connection(2 ,10) 1.0
connection(2 ,11) 1.0
connection(2 ,12) 1.0
connection(2 ,17) 0.0
connection(2 ,19) 1.0
connection(2 ,21) 0.0
connection(2 ,22) 1.0
connection(2 ,23) 0.0
connection(2 ,24) 0.0
connection(2 ,25) 1.0
connection(2 ,27) 0.0
connection(2 ,28) 0.0
connection(2 ,29) 1.0
connection(2 ,30) 0.0
connection(3 ,4) -0.0
connection(3 ,6) 1.0
connection(3 ,8) 0.0
connection(3 ,10) 0.0
connection(3 ,13) 0.0
connection(3 ,14) 0.0
connection(3 ,16) 0.0
connection(3 ,17) 1.0
connection(3 ,19) 0.0
connection(3 ,20) 1.0
connection(3 ,21) 1.0
connection(3 ,22) 0.0
connection(3 ,25) 0.0
connection(3 ,26) 0.0
connection(3 ,30) 1.0
connection(4 ,8) -0.0
connection(4 ,9) 1.0
connection(4 ,12) 0.0
connection(4 ,13) 0.0
connection(4 ,17) 1.0
connection(4 ,19) 0.0
connection(4 ,22) -0.0
connection(4 ,23) 1.0
connection(4 ,25) 0.0
connection(4 ,28) 1.0
connection(4 ,30) 1.0
connection(5 ,6) 0.0
connection(5 ,14) 1.0
connection(5 ,18) -0.0
connection(5 ,19) 1.0
connection(5 ,20) 0.0
connection(5 ,27) 0.0
connection(5 ,28) -0.0
connection(5 ,30) -0.0
connection(6 ,7) 0.0
connection(6 ,14) 1.0
connection(6 ,15) 0.0
connection(6 ,16) 1.0
connection(6 ,18) 0.0
connection(6 ,20) 0.0
connection(6 ,21) 0.0
connection(6 ,22) 1.0
connection(6 ,23) 0.0
connection(6 ,26) 1.0
connection(6 ,27) 0.0
connection(6 ,28) 0.0
connection(7 ,9) 0.0
connection(7 ,10) 1.0
connection(7 ,12) 1.0
connection(7 ,14) 1.0
connection(7 ,15) 0.0
connection(7 ,17) 0.0
connection(7 ,18) -0.0
connection(7 ,19) 1.0
connection(7 ,20) 0.0
connection(7 ,25) 1.0
connection(7 ,28) 0.0
connection(8 ,12) 0.0
connection(8 ,13) 0.0
connection(8 ,14) 0.0
connection(8 ,17) 1.0
connection(8 ,18) 1.0
connection(8 ,19) 0.0
connection(8 ,22) 0.0
connection(8 ,23) 1.0
connection(8 ,25) 0.0
connection(8 ,26) 0.0
connection(9 ,10) 1.0
connection(9 ,12) 1.0
connection(9 ,13) 1.0
connection(9 ,17) 0.0
connection(9 ,18) 0.0
connection(9 ,19) 1.0
connection(9 ,21) 0.0
connection(9 ,23) 0.0
connection(9 ,25) 1.0
connection(9 ,28) 0.0
connection(9 ,29) 1.0
connection(9 ,30) 0.0
connection(10 ,11) -0.0
connection(10 ,12) 0.0
connection(10 ,14) 0.0
connection(10 ,15) 1.0
connection(10 ,17) 1.0
connection(10 ,19) 0.0
connection(10 ,20) 1.0
connection(10 ,27) 1.0
connection(10 ,29) 0.0
connection(11 ,13) 0.0
connection(11 ,14) 0.0
connection(11 ,15) 1.0
connection(11 ,17) 1.0
connection(11 ,18) 1.0
connection(11 ,25) 0.0
connection(11 ,26) 0.0
connection(11 ,27) 1.0
connection(12 ,13) 0.0
connection(12 ,16) 0.0
connection(12 ,18) 1.0
connection(12 ,20) 1.0
connection(12 ,23) 1.0
connection(12 ,25) 0.0
connection(12 ,26) 0.0
connection(12 ,27) 1.0
connection(13 ,16) 0.0
connection(13 ,18) 1.0
connection(13 ,20) 1.0
connection(13 ,22) 0.0
connection(13 ,25) 0.0
connection(13 ,26) 0.0
connection(13 ,29) 0.0
connection(14 ,18) 1.0
connection(14 ,19) 0.0
connection(14 ,22) 0.0
connection(15 ,16) 1.0
connection(15 ,20) 0.0
connection(15 ,23) 0.0
connection(15 ,25) 1.0
connection(16 ,22) 0.0
connection(16 ,23) 1.0
connection(16 ,26) -0.0
connection(16 ,27) 1.0
connection(16 ,30) 1.0
connection(17 ,18) 0.0
connection(17 ,20) 0.0
connection(17 ,21) 0.0
connection(17 ,23) 0.0
connection(17 ,25) 1.0
connection(17 ,26) 1.0
connection(17 ,29) 1.0
connection(17 ,30) 0.0
connection(18 ,20) 0.0
connection(18 ,21) -0.0
connection(18 ,22) 1.0
connection(18 ,23) 0.0
connection(18 ,24) -0.0
connection(18 ,25) 1.0
connection(18 ,27) 0.0
connection(19 ,20) 1.0
connection(19 ,22) 0.0
connection(19 ,23) 1.0
connection(19 ,25) 0.0
connection(19 ,26) 0.0
connection(19 ,29) 0.0
connection(20 ,23) 0.0
connection(20 ,27) 0.0
connection(20 ,29) 1.0
connection(20 ,30) 0.0
connection(21 ,23) 0.0
connection(21 ,24) -0.0
connection(21 ,25) 1.0
connection(21 ,27) 0.0
connection(21 ,29) 1.0
connection(21 ,30) 0.0
connection(22 ,28) 1.0
connection(22 ,29) 0.0
connection(23 ,26) 1.0
connection(23 ,27) 0.0
connection(23 ,28) 0.0
connection(23 ,30) 0.0
connection(24 ,25) 1.0
connection(25 ,26) 0.0
connection(25 ,28) 1.0
connection(25 ,29) 0.0
connection(26 ,27) 1.0
connection(26 ,28) 1.0
connection(26 ,29) 0.0
connection(27 ,28) 0.0
connection(27 ,30) 0.0
connection(29 ,30) 1.0

In [12]:

    

#最大安定集合問題
def sep(V, E):
    model = Model("sep")
    x = {}
    for i in V:
        x[i] = model.addVar(vtype= "B", name= "picnic (%s)" %i)
    model.update()
    for (i,j) in E:
        model.addConstr(x[i] + x[j] <= 1)
    model.setObjective(quicksum(x[i] for i in V), -1)
    model.__data = x
    return model


    

In [13]:

    

if __name__ == "__main__":
    V, E = make_data(20,0.5)
    model = sep(V, E)
    model.optimize()
    print "OPT. Val =" , model.ObjVal
    
for v in model.getVars():
    print v.varname, v.X


    

    




Optimize a model with 92 rows, 20 columns and 184 nonzeros
Coefficient statistics:
  Matrix range    [1e+00, 1e+00]
  Objective range [1e+00, 1e+00]
  Bounds range    [1e+00, 1e+00]
  RHS range       [1e+00, 1e+00]
Found heuristic solution: objective 5
Presolve removed 68 rows and 3 columns
Presolve time: 0.00s
Presolved: 24 rows, 17 columns, 72 nonzeros
Variable types: 0 continuous, 17 integer (17 binary)

Root relaxation: objective 6.000000e+00, 16 iterations, 0.00 seconds

    Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

*    0     0               0       6.0000000    6.00000  0.00%     -    0s

Explored 0 nodes (23 simplex iterations) in 0.01 seconds
Thread count was 2 (of 4 available processors)

Optimal solution found (tolerance 1.00e-04)
Best objective 6.000000000000e+00, best bound 6.000000000000e+00, gap 0.0%
OPT. Val = 6.0
picnic (1) 1.0
picnic (2) 1.0
picnic (3) 0.0
picnic (4) 1.0
picnic (5) 0.0
picnic (6) -0.0
picnic (7) 0.0
picnic (8) 0.0
picnic (9) 1.0
picnic (10) -0.0
picnic (11) 0.0
picnic (12) -0.0
picnic (13) 0.0
picnic (14) 0.0
picnic (15) -0.0
picnic (16) 0.0
picnic (17) 1.0
picnic (18) 0.0
picnic (19) 0.0
picnic (20) 1.0

In [55]:

    

#グラフ彩色問題
def gcp(V, E, K):
    model = Model("gcp")
    x,y = {}, {}
    for k in range(K):
        y[k] = model.addVar(vtype = "B", name = "color(%s)" %k)
        for i in V:
            x[i,k] =  model.addVar(vtype = "B", name= "indi_color(%s, %s)" %(i,k))
    model.update()
    for i in V:
        model.addConstr(quicksum(x[i,k] for k in range(K) )== 1)
    for (i,j) in E:
        for k in range(K):
            model.addConstr(x[i,k] -x[j,k] <= y[k])
    for k in range(K-1):
        model.addConstr(y[k] >= y[k+1])
    model.setObjective(quicksum(y[k] for k in range(K)))
    model.update()
    model.__data = x
    print y
    return model


    

In [53]:

    

#解
#表示がおかしい
if __name__ == "__main__":
    V, E = make_data(4, 0.5)
    K = 4
    model = gcp(V, E, K)
    model.optimize()
    print "OPT.Val = ", model.ObjVal
     
    for v in model.getVars():
        print v.varname, v.X


    

    




Optimize a model with 15 rows, 20 columns and 46 nonzeros
Coefficient statistics:
  Matrix range    [1e+00, 1e+00]
  Objective range [1e+00, 1e+00]
  Bounds range    [1e+00, 1e+00]
  RHS range       [1e+00, 1e+00]
Found heuristic solution: objective 1
Presolve removed 1 rows and 4 columns
Presolve time: 0.00s
Presolved: 14 rows, 16 columns, 42 nonzeros
Variable types: 0 continuous, 16 integer (16 binary)

Root relaxation: objective 0.000000e+00, 3 iterations, 0.00 seconds

    Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

*    0     0               0       0.0000000    0.00000  0.00%     -    0s

Explored 0 nodes (3 simplex iterations) in 0.01 seconds
Thread count was 2 (of 4 available processors)

Optimal solution found (tolerance 1.00e-04)
Best objective 0.000000000000e+00, best bound 0.000000000000e+00, gap 0.0%
OPT.Val =  0.0
color(0) -0.0
indi_color(1, 0) -0.0
indi_color(2, 0) -0.0
indi_color(3, 0) 1.0
indi_color(4, 0) -0.0
color(1) -0.0
indi_color(1, 1) -0.0
indi_color(2, 1) -0.0
indi_color(3, 1) 0.0
indi_color(4, 1) -0.0
color(2) -0.0
indi_color(1, 2) 1.0
indi_color(2, 2) 1.0
indi_color(3, 2) 0.0
indi_color(4, 2) 1.0
color(3) -0.0
indi_color(1, 3) -0.0
indi_color(2, 3) -0.0
indi_color(3, 3) 0.0
indi_color(4, 3) -0.0

In [62]:

    

#グラフ彩色問題解法その2
def gcp_fixed(V, E, K):
    model = Model("gcp_fixed")
    x, z = {}, {}
    for i in V:
        for k in range(K):
            x[i,k] = model.addVar(vtype = "B", name = "indi_color(%s, %s)" %(i,k))
    for (i, j) in E:
        z[i,j] = model.addVar(vtype = "B", name = "bad_connection(%s, %s)" %(i,j))
    model.update()
    for i in V:
        model.addConstr(quicksum(x[i,k] for k in range(K)) == 1)
    for (i,j) in E:
        for k in range(k):
            model.addConstr(x[i,k] + x[j,k] <= 1 + z[i,j])
    model.setObjective(quicksum(z[i,j] for (i,j) in E))
    model.update()
    model.__data = x
    return model


    

In [78]:

    

#なにやら表示がおかしい
#解
if __name__ == "__main__":
    V, E = make_data(6, 0.5)
    K = 5
    model = gcp_fixed(V, E, K)
    model.optimize()
    print "OPT.Val = ", model.ObjVal
     
    for v in model.getVars():
        print v.varname, v.X


    

    




Optimize a model with 16 rows, 39 columns and 60 nonzeros
Coefficient statistics:
  Matrix range    [1e+00, 1e+00]
  Objective range [1e+00, 1e+00]
  Bounds range    [1e+00, 1e+00]
  RHS range       [1e+00, 1e+00]
Found heuristic solution: objective 0
Presolve removed 16 rows and 39 columns
Presolve time: 0.00s

Explored 0 nodes (0 simplex iterations) in 0.00 seconds
Thread count was 1 (of 4 available processors)

Optimal solution found (tolerance 1.00e-04)
Best objective 0.000000000000e+00, best bound 0.000000000000e+00, gap 0.0%
OPT.Val =  0.0
indi_color(1, 0) 0.0
indi_color(1, 1) 0.0
indi_color(1, 2) 0.0
indi_color(1, 3) 0.0
indi_color(1, 4) 1.0
indi_color(2, 0) 0.0
indi_color(2, 1) 0.0
indi_color(2, 2) 0.0
indi_color(2, 3) 0.0
indi_color(2, 4) 1.0
indi_color(3, 0) 0.0
indi_color(3, 1) 0.0
indi_color(3, 2) 0.0
indi_color(3, 3) 0.0
indi_color(3, 4) 1.0
indi_color(4, 0) 0.0
indi_color(4, 1) 0.0
indi_color(4, 2) 0.0
indi_color(4, 3) 0.0
indi_color(4, 4) 1.0
indi_color(5, 0) 1.0
indi_color(5, 1) 0.0
indi_color(5, 2) 0.0
indi_color(5, 3) 0.0
indi_color(5, 4) 0.0
indi_color(6, 0) 0.0
indi_color(6, 1) 0.0
indi_color(6, 2) 0.0
indi_color(6, 3) 0.0
indi_color(6, 4) 1.0
bad_connection(1, 3) 0.0
bad_connection(1, 6) 0.0
bad_connection(2, 3) 0.0
bad_connection(2, 4) 0.0
bad_connection(3, 4) 0.0
bad_connection(3, 5) 0.0
bad_connection(4, 5) 0.0
bad_connection(4, 6) 0.0
bad_connection(5, 6) 0.0

In [ ]: