Skip to content
Snippets Groups Projects
Select Git revision
  • master default protected
  • midway_progress
2 results
Blame Permalink
branching.py 11.36 KiB
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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248 






from globals import id,max_index_branching_candidates,max_constraint_branching_candidates,opt, branching_type,max_branching_search_time,max_branching_search_attempts,pyo,simple_index_branching,branching_lower_bound,branching_upper_bound,max_branching_set_length, constraint_branching_strategy
from logging_cvrp import log,timer
from statistics import stats
from instance_managing import solve
from pyomo.environ import value
from instance_managing import number_of_active_constraints
from instance_managing import set_lower_bound
from random import random, shuffle
from numpy import inf
from time import time


def branch(instance,instance_manager):
    #branches instance problem into two complementary sub problem instances over a specific index
    #adds two new instances that have been correctly initialised to instance_manager 
    #returns success of branching 
    log.subtitle("entering branching",instance.id)
    stats.update([instance.objective_value,instance.depth,number_of_active_constraints(instance.c_cap)],"start branching")
    initial_time = time()
    if branching_type == "index":
        branched_instances = branch_over_index(instance)
    if branching_type == "constraint":
        branched_instances = branch_over_constraint(instance)
    if branching_type == "integer_fix":
        branched_instances = integer_pseudo_branch(instance)
    #at this point, branching type should be valid since it is verified in the main
    
    if instance==None:
        return False

    #adding new instances to solving queue
    for instance in branched_instances:
        solver_success = solve(instance)
        if solver_success :
            set_lower_bound(instance)
            log.write("value of objective function is " +str(round(instance.objective_value,2)) + " for new instance " +list_to_string(instance.id)+" with lower bound "+str(instance.lower_bound),instance.id[:-1])
            instance_manager.add(instance)
    
    log.end_subtitle("end of branching ("+str(round(time()-initial_time,2))+"s)",instance.id)
    stats.update([instance.objective_value,instance.depth,number_of_active_constraints(instance.c_cap)],"end branching")
    return True


def branch_over_index(instance):
    #must return the instances that have been created an initialised
    index = find_branching_index(instance)
    if index==(-1,-1):
        log.write_timed("no branching index found, branch must be cut",instance.id)
        return None,None
    log.write_timed("branching index found over index "+str(index)+" with value "+str(round(instance.x[index].value,4)),instance.id)    
    instance.branching_indexes.append(index)
    
    #creating new instances ! recycling the old one into one of the new branches
    instance.x[index].fixed = True
    instance.branched_indexes.append(index)
    instance2 = instance.clone()
    instance.x[index].value = 0
    instance2.x[index].value = 1

    increment_depth_and_id([instance,instance2])
    
    log.write_awaiting_answer("finished creating new instances",instance.id)
    return [instance,instance2]


def branch_over_constraint(instance):
    branch_set = find_branching_set(instance)

    if branch_set == []:
        log.write("no branching set found, returning to a branching over index",instance.id)
        return branch_over_index(instance)

    log.write_timed("branching constraint found over set "+str(branch_set)+" with demand "+str(round(sum(instance.demands[i]/instance.capacity.value for i in branch_set),4))+" and coboundary "+str(sum( sum( instance.x[max(node,node_out),min(node,node_out)].value for node_out in instance.nodes if not(node_out in branch_set)) for node in branch_set)),instance.id) 
    
    instance.branching_sets.append(branch_set)
    instance2 = instance.clone()
    instance3 = instance.clone()
    expression = sum( sum( instance.x[max(i,j),min(i,j)] for j in instance.nodes if not(j in branch_set) ) for i in branch_set )
    instance.c_branch.add(expression==2)
    expression = sum( sum( instance2.x[max(i,j),min(i,j)] for j in instance2.nodes if not(j in branch_set) ) for i in branch_set ) #obligé car il faut remplacer les éléments de instance par ceux de instance2
    instance2.c_branch.add(expression==4)
    expression = sum( sum( instance3.x[max(i,j),min(i,j)] for j in instance3.nodes if not(j in branch_set) ) for i in branch_set ) #obligé car il faut remplacer les éléments de instance par ceux de instance2
    instance3.c_branch.add(expression>=6)

    instances = [instance,instance2,instance3]
    
    increment_depth_and_id(instances)

    log.write_awaiting_answer("finished creating new instances",instance.id)
    return instances


def integer_pseudo_branch(instance):
    index = find_branching_index(instance)
    instance.x[index].domain = pyo.NonNegativeIntegers
    instance.branched_indexes.append(index)
    instance.depth += 1
    instance.id = id.get_and_increment()
    log.write_awaiting_answer("finished creating new instance",instance.id)
    return [instance]
        
def increment_depth_and_id(instances):
    #global id
    id0 = instances[0].id
    depth = instances[0].depth
    for inst in instances: 
        inst.depth = depth+1
        #inst.id = id0+[id.get_and_increment()]   
        inst.id = id0+[instances.index(inst)] 


def find_branching_index(instance):
    #must return an index for branching
    #simple mode chooses the closest to 0.5, if false, it will look for the best branching index among max_branching_candidates number of candidates
    index = -1,-1
    if simple_index_branching: 
        dist = 1
        for bridge in instance.x.keys():
            if abs(instance.x[bridge].value-0.5)<dist:
                index = bridge
                dist = abs(instance.x[bridge].value-0.5)
    else:
        bridges = [(i,j) for i in range(instance.n.value) for j in range(i)]
        indexes = sorted(bridges,key = lambda bridge:min(abs(instance.x[bridge].value-0.5),abs(instance.x[bridge].value-0.75)))[:min(len(bridges),max_index_branching_candidates)] 
        best_boost = 0
        for ind in indexes:
            instance.x[ind].value=1
            instance.x[ind].fixed=True
            opt.solve(instance)
            a = value(instance.objective)
            instance.x[ind].value=0
            opt.solve(instance)
            b = value(instance.objective)
            c = min(a,b)
            if c>best_boost:
                best_boost = c
                index = ind
            instance.x[ind].fixed = False
    return index

def find_branching_set(instance):
    sets,count = [],0
    while count < max_branching_search_attempts:
        #print("none found, searched",len(sets.searched_sets),"sets")
        sets += find_sets_on_coboundary(instance)
        count += 1
    
    if sets == []:
        return []

    log.write("testing best possible branching between "+str(len(sets))+" sets",instance.id)

    if constraint_branching_strategy == "distance_to_depot":
        sets = sorted(sets, key = lambda a_set : sorted(a_set, key = lambda node : instance.costs[(node,0)])[0]+sorted(a_set, key = lambda node : instance.costs[(node,0)])[1], reverse = True )
        return sets[0]

    if constraint_branching_strategy == "demand":
        sets = sorted( sets, key = lambda a_set : sum( instance.demands[node] for node in a_set), reverse = True)
        return sets[0]

    if constraint_branching_strategy == "distance_demand_mix":
        sets = sorted(sets, key = lambda a_set : (sorted(a_set, key = lambda node : instance.costs[(node,0)])[0]+sorted(a_set, key = lambda node : instance.costs[(node,0)])[1])/instance.max_cost + sum( instance.demands[node] for node in a_set)/instance.capacity, reverse = True )
        return sets[0]

    if constraint_branching_strategy == "exhaustive":
        sets = sorted(sets, key = lambda a_set : sorted(a_set, key = lambda node : (instance.costs[(node,0)])[0]+sorted(a_set, key = lambda node : instance.costs[(node,0)])[1])/instance.max_cost + sum( instance.demands[node] for node in a_set)/instance.capacity, reverse = True )
        best_set,best_delta,initial_value = 0,0,instance.objective_value
        for branch_set in sets:
            expression = sum( sum( instance.x[max(i,j),min(i,j)] for j in instance.nodes if not(j in branch_set) ) for i in branch_set )
            instance.c_branch.add(expression==2)
            solve(instance,silent=True)
            delta = instance.objective_value - initial_value
            del(instance.c_branch[list(instance.c_branch.keys())[-1]])

            expression = sum( sum( instance.x[max(i,j),min(i,j)] for j in instance.nodes if not(j in branch_set) ) for i in branch_set )
            instance.c_branch.add(expression==4)
            solve(instance,silent=True)
            delta = min(delta,instance.objective_value - initial_value)
            del(instance.c_branch[list(instance.c_branch.keys())[-1]])

            if delta > best_delta:
                best_delta = delta
                best_set = branch_set

        log.write("resolving instance to its initial state after best gain found is "+str(best_delta),instance.id)
        solve(instance)
        return best_set   

    raise NameError("enter a valid constraint_branching_strategy") 

def find_sets_on_coboundary(instance,lb=branching_lower_bound,ub=branching_upper_bound): 
    sets = Search_set_manager(lb,ub)
    nodes = sorted(instance.nodes,key = lambda node : instance.costs[node,0],reverse=True)
    #for node in sorted(nodes,key = lambda node : nodes.index(node)*random()):
    for node in sorted(nodes,key = lambda node : random()):
        if node==0:
            continue
        a_set = [node]
        explore_set(instance,a_set,sets)
    return sets.valid_sets

def explore_set(instance,a_set,sets):
    #print("valid sets",len(sets.valid_sets),"and searched sets",len(sets.searched_sets),"current set demand",a_set.demand,"and current set coboundary",a_set.coboundary)
    if len(a_set)>max_branching_set_length or sets.is_invalid(a_set,instance) or len(sets.valid_sets)>5 or sets.timer.global_time()>max_branching_search_time:
        return
    sets.searched_sets.append(a_set)
    if sets.is_valid(a_set,instance):
        sets.record_set(a_set)
        return #THIS IS A TEST! 
    #print(a_set.demand,a_set.set)
    sorted_nodes = sorted(instance.nodes, key = lambda node : instance.costs[(a_set[-1],node)])
    #sorted_nodes = sorted(instance.nodes, key = lambda node : instance.x[max(a_set[-1],node),min(a_set[-1],node)].value if node!=a_set[-1] else inf)
    for node in sorted_nodes:
        if not(node in a_set) and node!=0:
            a_new_set = a_set.copy()
            a_new_set.append(node)
            explore_set(instance,a_new_set,sets)
    del(a_set)
    
class Search_set_manager():
    def __init__(self,lb,ub):
        self.valid_sets = []
        self.searched_sets = []
        self.ub = ub
        self.lb = lb
        self.timer = timer()
    
    def is_valid(self,a_set,instance):
        if self.lb<=coboundary(a_set,instance)<=self.ub:
            return True
        return False

    def is_invalid(self,a_set,instance):
        return sum(instance.demands[node] for node in a_set)/instance.capacity.value > 4 or a_set in self.searched_sets

    def record_set(self,a_set):
        self.valid_sets.append(a_set)


coboundary = lambda a_set,instance: sum( sum( instance.x[max(node,node_out),min(node,node_out)].value for node_out in instance.nodes if not(node_out in a_set) ) for node in a_set )
    

def list_to_string(ls):
	#returns more readible string of a list
	expr = ""
	for el in ls:
		expr += str(el)+"/"
	return expr[:-1]