-
Notifications
You must be signed in to change notification settings - Fork 0
/
main.py
90 lines (62 loc) · 2.65 KB
/
main.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
import xpress as xp
import networkx as nx
import matplotlib.pyplot as plt
import numpy as np
node_counter = 0
edges = []
best_solution = ((None, None), float('-inf'))
node_values = {}
def branch_and_bound(x1_range=(0, xp.infinity), x2_range=(0, xp.infinity)):
global node_counter, best_solution, edges, node_values
U34 = xp.problem()
# Variables
x1 = xp.var(lb=x1_range[0], ub=x1_range[1] if x1_range[1] is not None else xp.infinity)
x2 = xp.var(lb=x2_range[0], ub=x2_range[1] if x2_range[1] is not None else xp.infinity)
U34.addVariable(x1, x2)
# Constraints
U34.addConstraint(50 * x1 + 31 * x2 <= 250, 3 * x1 - 2 * x2 >= -4)
# Objective function
U34.setObjective(x1 + 0.64 * x2, sense=xp.maximize)
# Solve
U34.lpoptimize()
solution = U34.getSolution()
node_id = node_counter
node_counter += 1
if solution:
x1_val, x2_val = solution
objective = U34.getObjVal()
node_values[node_id] = (round(x1_val, 2), round(x2_val, 2), round(objective, 2))
if x1_val.is_integer() and x2_val.is_integer() and objective > best_solution[1]:
best_solution = ((x1_val, x2_val), objective)
if not x1_val.is_integer():
x1_floor = int(np.floor(x1_val))
edges.append((node_id, node_counter))
branch_and_bound(x1_range=(0, x1_floor), x2_range=x2_range)
edges.append((node_id, node_counter))
branch_and_bound(x1_range=(x1_floor+1, None), x2_range=x2_range)
if not x2_val.is_integer():
x2_floor = int(np.floor(x2_val))
edges.append((node_id, node_counter))
branch_and_bound(x1_range=x1_range, x2_range=(0, x2_floor))
edges.append((node_id, node_counter))
branch_and_bound(x1_range=x1_range, x2_range=(x2_floor+1, None))
def visualize_tree(edges, node_values):
G = nx.DiGraph()
G.add_edges_from(edges)
pos = nx.drawing.nx_agraph.graphviz_layout(G, prog='dot')
nx.draw_networkx_nodes(G, pos, node_color='white', node_size=1)
nx.draw_networkx_edges(G, pos)
labels = {}
for node, values in node_values.items():
labels[node] = f"x={values[0]}, y={values[1]}, z={values[2]}"
nx.draw_networkx_labels(G, pos, labels, bbox=dict(boxstyle='round,pad=0.3', edgecolor='black', facecolor='white'))
plt.show()
plt.savefig("tree.png")
# Execute the Branch-and-Bound algorithm and then print and visualize the result
def main():
branch_and_bound()
print(f"Best integer result: x={best_solution[0][0]}, y={best_solution[0][1]}")
# Visualize the tree
visualize_tree(edges, node_values)
if __name__ == "__main__":
main()