优化 | 使用凸包刻画约束满足问题中的alldifferent约束使模型更紧凑

from pyomo.environ import ConcreteModel, Set, Param, Var, Objective, minimize, Constraintfrom pyomo.opt import SolverFactoryimport pyomo.environ as pyoimport timedef read_assign_file(file_path):    with open(file_path, 'r') as file:        # 读取待分配物品数量n        n = int(file.readline().strip())        cost_matrix = []        current_row = []        count = 0        for line in file:            numbers = line.strip().split()            for num in numbers:                current_row.append(int(num))                count += 1                if count == n:                    cost_matrix.append(current_row)                    current_row = []                    count = 0
        return n, cost_matrix
def build_assignment_model(n, cost_matrix):    model = ConcreteModel()
    # 定义物品集合    model.nums = Set(initialize=range(n))
    # 定义决策变量x(i,j)，表示物品i是否分配给物品j，是二进制变量    model.assign = Var(model.nums, model.nums, within=pyo.Binary)
    # 定义成本参数，对应成本矩阵中的值    model.cost = Param(model.nums, model.nums, initialize=lambda model, i, j: cost_matrix[i][j])
    # 目标函数，最小化总成本    def total_cost_rule(model):        return sum(model.cost[i, j] * model.assign[i, j] for i in model.nums for j in model.nums)    model.obj = Objective(rule=total_cost_rule, sense=minimize)
    # 每个物品只能分配出去一次的约束    def assign_once_rule(model, i):        return sum(model.assign[i, j] for j in model.nums) == 1    model.assign_once = Constraint(model.nums, rule=assign_once_rule)
    # 每个物品最多只能接收一个物品的约束    def receive_once_rule(model, j):        return sum(model.assign[i, j] for i in model.nums) <= 1    model.receive_once = Constraint(model.nums, rule=receive_once_rule)
    return model
if __name__ == "__main__":    file_path = "assign400.txt"    n, cost_matrix = read_assign_file(file_path)    model = build_assignment_model(n, cost_matrix)
    # 使用SCIP求解器    solver = SolverFactory('SCIP')    t1=time.time()    result = solver.solve(model)    t2= time.time()    print(f"用时为{t2-t1}")    if result.solver.termination_condition == 'optimal':        print("找到最优解！")        optimal_cost = model.obj()        print("最优总成本:", optimal_cost)
        # 输出分配方案（示例，你可以根据需求调整展示格式等）        for i in range(n):            for j in range(n):                if model.assign[i, j].value == 1:                    print(f"物品{i}分配给物品{j}")    else:        print("未找到最优解，求解器终止状态:", result.solver.termination_condition)

from pyomo.environ import ConcreteModel, Set, Param, Var, Objective, minimize, Constraintfrom pyomo.opt import SolverFactoryimport pyomo.environ as pyoimport timedef read_assign_file(file_path):    with open(file_path, 'r') as file:        # 读取待分配物品数量n        n = int(file.readline().strip())        cost_matrix = []        current_row = []        count = 0        for line in file:            numbers = line.strip().split()            for num in numbers:                current_row.append(int(num))                count += 1                if count == n:                    cost_matrix.append(current_row)                    current_row = []                    count = 0
        return n, cost_matrix
def build_assignment_model(n, cost_matrix):    # 创建具体的模型实例    model = pyo.ConcreteModel("AssignmentProblem")    I = list(i+1 for i in range(n))    # 定义决策变量    model.y = pyo.Var(I, within=pyo.PositiveIntegers)
    # 约束条件1    def person_assigned_one_rule(model, h):        return sum(model.y[t] for t in range(1, h + 1)) >= (h - 1) * h / 2
    model.person_assigned_once = pyo.Constraint(I, rule=person_assigned_one_rule)
    # 约束条件2    def person_assigned_two_rule(model, h):        return sum(model.y[t] for t in range(1, h + 1)) <= h * (2 * len(I) - h + 1) / 2
    model.person_assigned_two = pyo.Constraint(I, rule=person_assigned_two_rule)
    # 目标函数：最小化总成本    def objective_rule(model):        val = 0        for i in I:            for j in I:                if model.y[i].value == j:                    val += cost_matrix[i-1][j-1]        return val
    model.obj = pyo.Objective(rule=objective_rule, sense=pyo.minimize)
    return model
if __name__ == "__main__":    file_path = "assign500.txt"    n, cost_matrix = read_assign_file(file_path)    model = build_assignment_model(n, cost_matrix)
    # 使用SCIP求解器    solver = SolverFactory('SCIP')    t1=time.time()    result = solver.solve(model)    t2= time.time()    print(f"用时为{t2-t1}")    if result.solver.termination_condition == 'optimal':        print("找到最优解！")        optimal_cost = model.obj()        print("最优总成本:", optimal_cost)