-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathoptimal_bricks2.py
94 lines (70 loc) · 14.7 KB
/
optimal_bricks2.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
import string
from collections import defaultdict
import gurobipy as gp
from gurobipy import GRB
# vertices_rows = 60
# vertices_columns = 60
def ordered_pair(v1, v2):
return (v1, v2) if v1 < v2 else (v2, v1)
adj_lists = {0: [], 1: [497, 456], 2: [68, 144, 497], 3: [11, 494, 484, 16], 4: [200, 421], 5: [496], 6: [487], 7: [496, 489, 179], 8: [488, 487, 161], 9: [401, 432, 492], 10: [493, 12], 11: [299, 258, 493, 3], 12: [203, 485, 10, 414], 13: [387, 34, 483], 14: [27, 28, 477], 15: [20, 471, 482, 476], 16: [21, 299, 3, 478], 17: [203, 308, 479, 485], 18: [318, 257, 19, 480], 19: [22, 465, 481, 18], 20: [15, 470, 304, 302], 21: [16, 464, 317, 300], 22: [443, 19, 257, 256], 23: [395, 354], 24: [49, 161, 487, 469], 25: [381, 382], 26: [339, 403], 27: [14, 461, 313, 208], 28: [215, 462, 14, 208], 29: [275, 122, 460, 439], 30: [86, 440, 462, 215], 31: [49, 169, 210, 161], 32: [117, 410, 413, 116], 33: [304, 470, 386, 75], 34: [305, 495, 13, 35], 35: [214, 323, 34, 387], 36: [340, 85], 37: [441, 343, 331, 291], 38: [309, 183, 344, 445], 39: [159, 40, 382, 381], 40: [39, 160, 196, 41], 41: [382, 40, 195, 334], 42: [229, 162, 43, 47], 43: [42, 44, 45, 310], 44: [43, 162, 163, 46], 45: [303, 43, 46, 279], 46: [44, 104, 280, 45], 47: [310, 314, 230, 42], 48: [453, 361, 64, 50], 49: [50, 31, 24, 453], 50: [48, 66, 169, 49], 51: [54, 57, 56, 52], 52: [51, 81, 80, 53], 53: [52, 226, 223, 54], 54: [51, 53, 91, 55], 55: [218, 57, 54, 93], 56: [81, 51, 192, 189], 57: [219, 192, 51, 55], 58: [62, 60, 61, 95], 59: [60, 236, 266, 61], 60: [58, 92, 287, 59], 61: [59, 326, 94, 58], 62: [92, 58, 63, 93], 63: [95, 272, 217, 62], 64: [358, 66, 48, 65], 65: [64, 361, 360, 359], 66: [357, 170, 50, 64], 67: [380, 127, 159, 381], 68: [219, 2, 69, 192], 69: [158, 191, 68], 70: [74, 73, 312, 71], 71: [337, 151, 70, 273], 72: [239, 73, 74, 274], 73: [75, 70, 72, 242], 74: [70, 151, 336, 72], 75: [73, 292, 33, 312], 76: [77, 78, 349, 348], 77: [165, 181, 182, 76], 78: [76, 182, 224, 225], 79: [80, 81, 352, 351], 80: [79, 350, 226, 52], 81: [52, 56, 82, 79], 82: [352, 81, 189, 353], 83: [86, 84, 89, 88], 84: [83, 87, 307, 329], 85: [440, 86, 88, 36], 86: [85, 30, 87, 83], 87: [306, 84, 86, 215], 88: [90, 340, 85, 83], 89: [83, 329, 330, 90], 90: [89, 331, 145, 88], 91: [93, 54, 223, 92], 92: [60, 62, 91, 227], 93: [217, 55, 91, 62], 94: [95, 61, 222, 220], 95: [94, 96, 63, 58], 96: [221, 272, 95, 220], 97: [100, 98, 247, 101], 98: [97, 102, 246, 99], 99: [98, 333, 248, 247], 100: [153, 154, 102, 97], 101: [147, 153, 97, 213], 102: [244, 98, 100, 173], 103: [105, 107, 325, 245], 104: [163, 325, 107, 46], 105: [106, 103, 243, 216], 106: [201, 107, 105, 200], 107: [104, 103, 106, 280], 108: [272, 364, 143, 217], 109: [418, 417, 110, 254], 110: [364, 272, 221, 109], 111: [126, 113, 112, 132], 112: [238, 111, 114, 424], 113: [111, 127, 115, 114], 114: [112, 113, 283, 425], 115: [113, 250, 251, 283], 116: [370, 177, 32, 179], 117: [32, 177, 211, 371], 118: [119, 173, 172, 120], 119: [366, 365, 282, 118], 120: [130, 121, 366, 118], 121: [368, 367, 120, 131], 122: [461, 29, 276, 313], 123: [125, 124, 198, 355], 124: [123, 202, 171, 170], 125: [354, 184, 202, 123], 126: [111, 128, 159, 127], 127: [250, 113, 126, 67], 128: [133, 160, 126, 132], 129: [132, 131, 233, 133], 130: [172, 233, 131, 120], 131: [129, 238, 121, 130], 132: [128, 111, 238, 129], 133: [129, 298, 197, 128], 134: [293, 149, 137, 136], 135: [136, 298, 284, 293], 136: [135, 134, 240, 241], 137: [242, 240, 134, 148], 138: [343, 342, 145, 331], 139: [375, 140, 141, 142], 140: [164, 372, 139, 374], 141: [372, 371, 211, 139], 142: [212, 376, 139, 211], 143: [108, 363, 144, 218], 144: [219, 143, 415, 2], 145: [340, 90, 138, 278], 146: [149, 147, 301, 150], 147: [101, 214, 146, 155], 148: [137, 149, 150, 292], 149: [155, 146, 148, 134], 150: [146, 302, 304, 148], 151: [74, 71, 437, 436], 152: [154, 153, 293, 284], 153: [155, 152, 100, 101], 154: [173, 100, 152, 172], 155: [293, 153, 147, 149], 156: [202, 158, 157, 171], 157: [210, 156, 362, 455], 158: [156, 190, 69, 362], 159: [126, 160, 39, 67], 160: [197, 40, 159, 128], 161: [31, 454, 8, 24], 162: [294, 295, 44, 42], 163: [104, 44, 295, 324], 164: [429, 140, 373, 430], 165: [166, 167, 77, 348], 166: [346, 183, 165, 347], 167: [165, 183, 309, 181], 168: [282, 365, 216, 243], 169: [50, 170, 171, 31], 170: [198, 124, 169, 66], 171: [124, 156, 210, 169], 172: [130, 118, 154, 284], 173: [102, 154, 118, 282], 174: [176, 175, 178, 251], 175: [212, 211, 177, 174], 176: [174, 237, 378, 212], 177: [117, 116, 178, 175], 178: [174, 177, 370, 281], 179: [7, 428, 116, 413], 180: [234, 182, 181, 256], 181: [77, 167, 271, 180], 182: [180, 288, 78, 77], 183: [311, 38, 167, 166], 184: [190, 125, 353, 189], 185: [188, 255, 277, 186], 186: [201, 187, 185, 279], 187: [188, 186, 199, 420], 188: [185, 187, 419, 252], 189: [56, 191, 184, 82], 190: [191, 158, 202, 184], 191: [69, 190, 189, 192], 192: [56, 57, 68, 191], 193: [240, 194, 196, 241], 194: [274, 195, 193, 239], 195: [41, 196, 194, 335], 196: [193, 195, 40, 197], 197: [196, 160, 133, 241], 198: [357, 356, 123, 170], 199: [200, 187, 201], 200: [4, 199, 106, 216], 201: [199, 186, 280, 106], 202: [190, 156, 124, 125], 203: [204, 205, 17, 12], 204: [414, 321, 319, 203], 205: [326, 308, 203, 319], 206: [209, 207, 296, 297], 207: [215, 208, 206, 306], 208: [207, 28, 27, 296], 209: [294, 306, 206, 295], 210: [31, 171, 157, 454], 211: [175, 142, 141, 117], 212: [175, 176, 377, 142], 213: [323, 214, 101, 247], 214: [213, 35, 301, 147], 215: [28, 207, 87, 30], 216: [200, 105, 168, 421], 217: [108, 218, 93, 63], 218: [55, 217, 143, 219], 219: [68, 57, 218, 144], 220: [96, 94, 286, 285], 221: [285, 254, 110, 96], 222: [319, 286, 94, 326], 223: [91, 53, 224, 227], 224: [223, 226, 78, 288], 225: [226, 350, 349, 78], 226: [224, 53, 80, 225], 227: [288, 287, 92, 223], 228: [229, 231, 329, 307], 229: [42, 230, 228, 294], 230: [229, 47, 315, 231], 231: [232, 228, 230, 317], 232: [330, 329, 231, 290], 233: [129, 130, 284, 298], 234: [180, 235, 287, 288], 235: [257, 236, 234, 256], 236: [59, 287, 235, 265], 237: [250, 379, 176, 251], 238: [112, 368, 131, 132], 239: [240, 242, 72, 194], 240: [239, 193, 136, 137], 241: [298, 136, 193, 197], 242: [73, 239, 137, 292], 243: [105, 245, 244, 168], 244: [282, 243, 246, 102], 245: [332, 246, 243, 103], 246: [245, 333, 98, 244], 247: [249, 213, 97, 99], 248: [99, 268, 276, 249], 249: [247, 248, 275, 323], 250: [237, 115, 127, 380], 251: [237, 174, 281, 115], 252: [254, 255, 188, 418], 253: [262, 255, 254, 285], 254: [221, 253, 252, 109], 255: [252, 253, 260, 185], 256: [235, 180, 271, 22], 257: [265, 235, 22, 18], 258: [11, 259, 321, 414], 259: [316, 322, 258, 299], 260: [255, 262, 289, 277], 261: [262, 264, 328, 289], 262: [261, 260, 253, 263], 263: [286, 264, 262, 285], 264: [263, 320, 322, 261], 265: [236, 257, 318, 266], 266: [265, 308, 326, 59], 267: [268, 269, 313, 276], 268: [248, 333, 270, 267], 269: [296, 267, 270, 297], 270: [268, 332, 324, 269], 271: [256, 181, 309, 443], 272: [63, 96, 110, 108], 273: [71, 312, 339, 338], 274: [336, 335, 194, 72], 275: [276, 29, 305, 249], 276: [248, 267, 122, 275], 277: [260, 303, 279, 185], 278: [341, 145, 342], 279: [45, 280, 186, 277], 280: [279, 46, 107, 201], 281: [283, 251, 178, 369], 282: [244, 173, 119, 168], 283: [281, 426, 114, 115], 284: [233, 172, 152, 135], 285: [263, 253, 221, 220], 286: [220, 222, 320, 263], 287: [234, 236, 60, 227], 288: [227, 224, 182, 234], 289: [260, 261, 327, 303], 290: [317, 464, 291, 232], 291: [290, 442, 37, 330], 292: [242, 148, 304, 75], 293: [152, 155, 134, 135], 294: [229, 307, 209, 162], 295: [209, 297, 163, 162], 296: [206, 208, 313, 269], 297: [269, 324, 295, 206], 298: [133, 233, 135, 241], 299: [259, 11, 16, 300], 300: [315, 316, 299, 21], 301: [387, 302, 146, 214], 302: [150, 301, 471, 20], 303: [310, 45, 277, 289], 304: [20, 33, 292, 150], 305: [275, 439, 34, 323], 306: [207, 209, 307, 87], 307: [84, 306, 294, 228], 308: [266, 318, 17, 205], 309: [444, 271, 167, 38], 310: [47, 43, 303, 327], 311: [345, 344, 183, 346], 312: [70, 75, 386, 273], 313: [267, 296, 27, 122], 314: [316, 315, 47, 327], 315: [230, 314, 300, 317], 316: [314, 328, 259, 300], 317: [315, 21, 290, 231], 318: [479, 308, 265, 18], 319: [320, 222, 205, 204], 320: [321, 264, 286, 319], 321: [320, 204, 258, 322], 322: [328, 264, 321, 259], 323: [213, 249, 305, 35], 324: [163, 297, 270, 325], 325: [103, 104, 324, 332], 326: [222, 61, 266, 205], 327: [314, 310, 289, 328], 328: [322, 316, 327, 261], 329: [228, 232, 89, 84], 330: [291, 331, 89, 232], 331: [90, 330, 37, 138], 332: [333, 245, 325, 270], 333: [99, 246, 332, 268], 334: [41, 335], 335: [195, 274, 435, 334], 336: [274, 74, 436, 435], 337: [71, 338, 383, 437], 338: [273, 385, 384, 337], 339: [273, 386, 26, 385], 340: [88, 145, 341, 36], 341: [278, 340], 342: [278, 138, 388], 343: [138, 37, 388], 344: [311, 389, 446, 38], 345: [311, 391, 390, 389], 346: [311, 166, 412, 391], 347: [166, 348, 392, 412], 348: [165, 76, 393, 347], 349: [76, 225, 394, 393], 350: [225, 80, 351, 394], 351: [79, 447, 350], 352: [79, 82, 395, 447], 353: [82, 184, 354, 395], 354: [125, 355, 23, 353], 355: [123, 356, 354], 356: [198, 396, 355], 357: [198, 66, 358, 396], 358: [64, 359, 397, 357], 359: [65, 399, 398, 358], 360: [65, 451, 450, 399], 361: [65, 48, 452, 451], 362: [157, 158, 456], 363: [143, 364, 416, 415], 364: [108, 110, 417, 363], 365: [168, 119, 422, 421], 366: [119, 120, 367, 422], 367: [121, 423, 366], 368: [121, 238, 424, 423], 369: [281, 370, 427, 426], 370: [178, 116, 428, 369], 371: [117, 141, 400, 410], 372: [141, 140, 429, 400], 373: [164, 374, 432, 401], 374: [140, 375, 373], 375: [139, 376, 374], 376: [142, 377, 375], 377: [212, 378, 376], 378: [176, 379, 433, 377], 379: [237, 380, 434, 378], 380: [250, 67, 402, 379], 381: [67, 39, 25, 402], 382: [39, 41, 25], 383: [337, 384, 438], 384: [338, 383], 385: [338, 339], 386: [339, 312, 33, 403], 387: [471, 301, 35, 13], 388: [342, 343], 389: [344, 345, 404], 390: [345, 405, 404], 391: [345, 346, 405], 392: [347, 393], 393: [348, 349, 392], 394: [349, 350], 395: [352, 353, 23], 396: [356, 357, 397], 397: [358, 398, 396], 398: [359, 406, 397], 399: [359, 360, 407, 406], 400: [371, 372], 401: [430, 373, 9, 431], 402: [380, 381, 434], 403: [26, 386, 470, 475], 404: [389, 390], 405: [390, 391], 406: [398, 399, 408], 407: [399, 450, 409, 408], 408: [406, 407, 411], 409: [407, 449, 448, 411], 410: [32, 371], 411: [408, 409, 468, 467], 412: [346, 347], 413: [179, 32, 496], 414: [493, 258, 204, 12], 415: [144, 363, 497], 416: [363, 417], 417: [364, 109, 457, 416], 418: [109, 252, 419, 457], 419: [188, 420, 418], 420: [187, 419], 421: [216, 365, 4], 422: [365, 366], 423: [367, 368], 424: [368, 112, 425], 425: [114, 426, 424], 426: [283, 369, 458, 425], 427: [369, 428, 458], 428: [370, 179, 489, 427], 429: [372, 164], 430: [164, 401], 431: [401, 492, 459], 432: [373, 9], 433: [378, 434], 434: [379, 402, 433], 435: [335, 336], 436: [336, 151], 437: [151, 337, 438], 438: [383, 437], 439: [305, 29, 495], 440: [85, 30], 441: [37, 442], 442: [291, 464, 463, 441], 443: [271, 444, 465, 22], 444: [309, 445, 466, 443], 445: [38, 446, 444], 446: [344, 445], 447: [351, 352], 448: [409, 468], 449: [409, 450], 450: [407, 360, 449], 451: [360, 361], 452: [361, 453], 453: [48, 49, 469, 452], 454: [161, 210, 455, 488], 455: [157, 456, 454], 456: [362, 1, 455], 457: [417, 418], 458: [426, 427], 459: [431, 474], 460: [29, 461], 461: [122, 27, 477, 460], 462: [30, 28], 463: [442, 478], 464: [442, 290, 21, 478], 465: [443, 466, 19], 466: [444, 465], 467: [411, 472], 468: [411, 448, 473, 472], 469: [453, 24], 470: [476, 403, 33, 20], 471: [15, 302, 387, 483], 472: [467, 468, 486], 473: [468, 486], 474: [459, 492, 491, 490], 475: [403, 476], 476: [470, 15, 475], 477: [461, 14], 478: [463, 464, 16, 484], 479: [318, 480, 17], 480: [18, 481, 479], 481: [19, 480], 482: [15, 483], 483: [471, 13, 482], 484: [478, 3], 485: [17, 12], 486: [472, 473], 487: [24, 8, 6], 488: [454, 8], 489: [428, 7], 490: [474], 491: [474], 492: [474, 431, 9], 493: [494, 11, 414, 10], 494: [493, 3], 495: [439, 34], 496: [7, 5, 413], 497: [1, 2, 415]}
edges = set()
# a dictionary whose key is the node(mesh face)
# value is the edge(two adjacent mesh faces)
edges_by_vert = defaultdict(set)
for a in adj_lists.keys():
for b in adj_lists[a]:
e = ordered_pair(a, b)
edges.add(e)
edges_by_vert[a].add(e)
edges_by_vert[b].add(e)
# print(len(adj_lists), 'Vertexes')
# print('Edges:', edges)
try:
# initiate the model
m = gp.Model("optimal_bricks")
# add variables, all the edges are variables
edges_picked_vars = m.addVars(edges, vtype=GRB.BINARY, lb = 0, ub = 1)
# add constraint, every node can only be connected once
for a in edges_by_vert.keys():
m.addConstr(sum([edges_picked_vars[e] for e in edges_by_vert[a]]) <= 1, str(a))
# Find pairs of edges which are directly next to each other and parallel, e.g. (a,b) and (c,d), and (a,c) and (b,d):
# a-b
# | |
# c-d
# We want to avoid such combination of edges because it is undesirable to have bricks next to each other like this.
# The code below finds the pair (a,b) & (c,d)
edge_neighbors = set()
for a in adj_lists.keys():
for b in adj_lists[a]:
for c in adj_lists[a]:
if b != c:
for d in adj_lists[c]:
if d in adj_lists[b]:
e1 = ordered_pair(a, b)
e2 = ordered_pair(c, d)
edge_neighbors.add(ordered_pair(e1, e2))
parallel_brick_pairs_vars = []
for e1, e2 in edge_neighbors:
edge_str = str(f"({e1})+({e2})")
edge_pair_exists = m.addVar(lb=0, ub=1, name=edge_str)
m.addConstr(edge_pair_exists >= edges_picked_vars[e1] + edges_picked_vars[e2] - 1, "constr_" + edge_str)
parallel_brick_pairs_vars.append(edge_pair_exists)
print(len(parallel_brick_pairs_vars))
# It seems more important to minimize the number of irregular bricks, so we assign a 5x higher weight to this part of
# the objective function
m.setObjective(sum(edges_picked_vars.values()) - .5 * sum(parallel_brick_pairs_vars), GRB.MAXIMIZE)
m.optimize()
print('Obj: %g' % m.ObjVal)
bricks_cnt = sum(int(v.X) for v in edges_picked_vars.values())
print(f"{bricks_cnt} bricks, {len(adj_lists) - bricks_cnt*2} unconnected vertex(es)")
parallel_bricks_cnt = sum(round(v.X) for v in parallel_brick_pairs_vars)
print(f"{parallel_bricks_cnt} pair(s) of parallel bricks")
chosen_edges = []
for e in edges_picked_vars.keys():
if edges_picked_vars[e].X == 1:
chosen_edges.append(e)
print(chosen_edges)
except gp.GurobiError as e:
print('Error code ' + str(e.errno) + ': ' + str(e))
except AttributeError:
print('Encountered an attribute error')