# =============================================================================
"""Build Master Problem"""
# =============================================================================
import coptpy
import sys
import os
class MasterProblem:
def __init__(self, Data):
self.column_index = Data.cur_columns.index.values # 子列的索引值
self.column_cost = Data.cur_columns['column_cost'].values
self.column_cover = Data.cur_columns['column_cover'].values
self.item_index = Data.demand.index.values
self.item_size = Data.demand['item_size'].values
self.item_demand = Data.demand['demand'].values
self.Data = Data
## 模型相关属性
sys.stdout = open(os.devnull, 'w')
self.env = coptpy.Envr()
self.model = self.env.createModel("MasterProblem")
sys.stdout = sys.__stdout__
## 存储求解结果
self.obj_value = 0 # 模型求解结果
self.consName_2_dual = {} # 存储各个约束的对偶变量的值
## 建立模型
self.var_use_times = {} # 每个 column 被选择的次数
self.origin_integer = []
self.add_column_num = 0
self.build_model()
def build_model(self):
"""variables"""
## 每个 column 都对应一个变量
for i in self.column_index:
self.var_use_times[i] = self.model.addVar(lb=0, ub=coptpy.COPT.INFINITY,
vtype=coptpy.COPT.INTEGER,
name=f"{i}_column_use_times")
## records the integer variables
for var_ in self.model.getVars():
if var_.vtype == coptpy.COPT.INTEGER:
self.origin_integer.append(var_.name)
"""constraints"""
## 每个需求都需要被满足
for i in self.item_index:
self.model.addConstr(coptpy.quicksum(self.column_cover[column_][i] * self.var_use_times[column_]
for column_ in self.column_index) >= self.item_demand[i], name=f"satisfy_demand_{i}")
"""objective"""
self.model.setObjective(coptpy.quicksum(self.var_use_times[column_] * self.column_cost[column_]
for column_ in self.column_index), sense=coptpy.COPT.MINIMIZE)
def solve_relaxed_model(self):
"""relaxed integer variables to continuous variables"""
for varName in self.origin_integer:
int_var = self.model.getVarByName(varName)
int_var.vtype = coptpy.COPT.CONTINUOUS
"""solve the relaxed problem"""
self.model.setParam('logging', 0)
self.model.solve()
"""指定约束名的约束的对偶变量"""
if self.model.status == coptpy.COPT.OPTIMAL:
self.obj_value = self.model.objVal
for i in self.item_index:
cons_name = f"satisfy_demand_{i}"
cons = self.model.getConstrByName(cons_name) # 定义约束时要显示出参数 "name"
self.consName_2_dual[cons_name] = self.model.getInfo(coptpy.COPT.info.Dual, cons)
else:
print("主问题的线性松弛问题找不到可行解!")
def addColumn(self, newColumn_cost, item_2_newCover):
print("测试:", self.Data.cur_columns)
self.Data.cur_columns.loc[len(self.Data.cur_columns)] = [1, [int(item_2_newCover[x]) for x in item_2_newCover]]
print(f"cur_columns--------------\n{self.Data.cur_columns}")
print(item_2_newCover)
"""add the new column"""
add_column_coef = []
for i in self.item_index:
item_coef = item_2_newCover[i]
item_cons = self.model.getConstrByName(f"satisfy_demand_{i}")
add_column_coef.append((item_cons, item_coef))
add_column = coptpy.Column(add_column_coef)
"""add new column as add a new var to model: constraints & objective"""
self.add_column_num += 1
newColumn_name = f"new_column_{self.add_column_num}"
self.model.addVar(vtype=coptpy.COPT.CONTINUOUS, lb=0,
obj=newColumn_cost, column=add_column,
name=newColumn_name)
self.origin_integer.append(newColumn_name)
def solve_master_problem(self, TimeLimit=100, GapLimit=0.05):
"""restore the origin variables"""
for varName in self.origin_integer:
int_var = self.model.getVarByName(varName)
int_var.vtype = coptpy.COPT.INTEGER
"""solve master problem"""
self.model.setParam('logging', 0)
self.model.setParam('timelimit', TimeLimit)
self.model.setParam('RelGap', GapLimit)
self.model.solve()
def print_result(self):
"""print the result"""
if self.model.status == coptpy.COPT.OPTIMAL:
for idx, var_ in enumerate(self.model.getVars()):
if var_.x != 0:
keys = ["piece size " + str(i) for i in self.Data.demand['item_size']]
values = self.Data.cur_columns.iloc[idx, 1]
dictionary = dict(zip(keys, values)) # display the column
print(f"The column {dictionary} is used {int(var_.x)} times.")
print(f"The objective is {self.model.objVal}.")
else:
print("主问题找不到可行的整数解!")