Алгоритм ветвей и границ ⇐ Python

[Anonymous]

Я пытаюсь реализовать алгоритм ветвей и границ, чтобы найти оптимальное решение транспортной задачи с ограничениями по загрузке грузовиков. Другими словами, у меня есть 6-тонные грузовики, и я использую их для перевозки, чтобы найти минимальную общую стоимость перевозки.
Вот мой код:

Код: Выделить всё

import numpy as np
from scipy.optimize import linprog

# Global variables
node_counter = 0
best_solution = (None, float('inf'))  # (solution, total cost)
truck_capacity = 6  # in tons

def calculate_total_cost(solution, cost_per_ton):
"""
Calculate the total transportation cost considering truck capacity.
"""
total_cost = 0
for i, flow in enumerate(solution):
trucks_needed = int(np.ceil(flow / truck_capacity))  # Number of full truckloads
total_cost += trucks_needed * truck_capacity * cost_per_ton[i]  # Cost for full truckloads
return total_cost

def branch_and_bound(bounds, depth=0):
global node_counter, best_solution

# Transportation cost matrix (flattened)
cost_per_ton = np.array([
10, 8, 5, 9, 16,
4, 3, 4, 11, 12,
5, 10, 29, 7, 6,
9, 2, 4, 1, 3
])

# Supply constraints
A_ub = np.zeros((4, 20))
A_ub[0, :5] = 1
A_ub[1, 5:10] = 1
A_ub[2, 10:15] = 1
A_ub[3, 15:] = 1
b_ub = [17, 8, 10, 9]

# Demand constraints
A_eq = np.zeros((5, 20))
for i in range(5):
A_eq[i, i::5] = 1
b_eq = [6, 15, 7, 8, 8]

# Solve LP relaxation
res = linprog(cost_per_ton, A_ub=A_ub, b_ub=b_ub, A_eq=A_eq, b_eq=b_eq, bounds=bounds, method='highs')
node_counter += 1

if res.success:
solution = res.x
total_cost = calculate_total_cost(solution, cost_per_ton)

# Debug output
print(f"Depth {depth}: Solution = {solution}, Total Cost = {total_cost}")

# Check for a new best integer solution
if all(val.is_integer() for val in solution):
if total_cost <  best_solution[1]:
print(f"New best integer solution found at Depth {depth}: Total Cost = {total_cost}")
best_solution = (solution, total_cost)
return  # Stop branching as the solution is already integer

# Branch on all fractional variables
for i, val in enumerate(solution):
if not val.is_integer():
# Floor and ceil values respecting truck capacity
floor_val = (int(val // truck_capacity)) * truck_capacity
ceil_val = floor_val + truck_capacity

# Branch lower: restrict variable to [0, floor_val]
new_bounds_lower = bounds[:]
new_bounds_lower[i] = (0, floor_val)
print(f"Branching Lower on variable {i} at Depth {depth}")
branch_and_bound(new_bounds_lower, depth + 1)

# Branch upper: restrict variable to [ceil_val, None]
new_bounds_upper = bounds[:]
new_bounds_upper[i] = (ceil_val, None)
print(f"Branching Upper on variable {i} at Depth {depth}")
branch_and_bound(new_bounds_upper, depth + 1)

break  # Ensure this branch handles only one variable at a time

# Initialize bounds
initial_bounds = [(0, None)] * 20

# Execute the Branch-and-Bound algorithm
branch_and_bound(initial_bounds)

# Format the best solution for output
if best_solution[0] is not None:
solution_matrix = np.array(best_solution[0]).reshape(4, 5)  # 4 sources x 5 destinations
print(f"Best integer result (matrix):\n{solution_matrix}")
else:
print("No feasible integer solution found.")

print(f"Objective value (considering truck capacity): {best_solution[1]}")
print(f"Number of explored nodes: {node_counter}")

Я получаю решение:
Лучший целочисленный результат (матрица):




D1
D2
D3
D4




S1
0
10
7
0


S2
3
5
0
0

S3
3
0
0
0


S4
0
0
0
8



Цельное значение (с учетом грузоподъемности грузовика) : 330$.
Количество исследованных узлов: 1
К сожалению, ответ неверный, потому что я решил проблему другим методом, и для 6-тонных грузовиков распределение и общая цена составляют:
Общая цена: 276,00 долларов США




< th>D1
D2
D3
D4




S1
0
6
5
6


S2
0
6
2< /td>
0


S3
6
0
0
0


S4
03
0
2

Код: Выделить всё

import pandas as pd
import pulp

truck_capacity = 6
suppliers = pd.RangeIndex(name='supplier', stop=4)
consumers = pd.RangeIndex(name='consumer', stop=5)

supply = pd.Series(
name='supply',
index=suppliers,
data=(17, 8, 10, 9),
)
demand = pd.Series(
name='demand',
index=consumers,
data=(6, 15, 7, 8, 8),
)
price_per_tonne = pd.DataFrame(
index=suppliers, columns=consumers,
data=(
(10,  8,  5,  9, 16),
( 4,  3,  4, 11, 12),
( 5, 10, 29,  7,  6),
( 9,  2,  4,  1,  3),
),
).stack()
price_per_tonne.name = 'price'

flow = pd.DataFrame(
index=suppliers, columns=consumers,
data=pulp.LpVariable.matrix(
name='flow_s%d_c%d', cat=pulp.LpContinuous, lowBound=0,
indices=(suppliers, consumers),
),
).stack()
flow.name = 'flow'

trucks = pd.DataFrame(
index=suppliers, columns=consumers,
data=pulp.LpVariable.matrix(
name='trucks_s%d_c%d', cat=pulp.LpInteger, lowBound=0,
indices=(suppliers, consumers),
)
).stack()
trucks.name = 'trucks'

price = truck_capacity * pulp.lpDot(price_per_tonne, trucks)
prob = pulp.LpProblem(name='transportation', sense=pulp.LpMinimize)
prob.setObjective(price)

# The flow must not exceed the supply
for supplier, group in flow.groupby('supplier'):
prob.addConstraint(
name=f'flow_supply_s{supplier}',
constraint=pulp.lpSum(group) 

Подробнее здесь: [url]https://stackoverflow.com/questions/79230442/branch-and-bound-algorithm[/url]