fixanddive.py
# !实现一个简单的MIP启发式算法狗万app足彩放松模型，基于分数性对变量进行排序，并修正最接近整数变量的25%的分数变量。重复，直到松弛是整数可行或线性不可行的。import sys import gurobipy as gp from gurobipy import GRB # Key函数，用于根据松弛分值对变量进行排序。Xreturn abs(sol-int(sol+0.5)) if len(sys.argv) < 2: print('Usage: fixanddive.py filename') sys.exit(0) # Read model model = gp.read(sys.argv[1]) # Collect integer variables and relax them intvars = [] for v in model.getVars(): if v.VType != GRB.CONTINUOUS: intvars += [v] v.VType = GRB.CONTINUOUS model.Params.OutputFlag = 0 model.optimize() # Perform multiple iterations. In each iteration, identify the first # quartile of integer variables that are closest to an integer value in the # relaxation, fix them to the nearest integer, and repeat. for iter in range(1000): # create a list of fractional variables, sorted in order of increasing # distance from the relaxation solution to the nearest integer value fractional = [] for v in intvars: sol = v.X if abs(sol - int(sol+0.5)) > 1e-5: fractional += [v] fractional.sort(key=sortkey) print('Iteration %d, obj %g, fractional %d' % (iter, model.ObjVal, len(fractional))) if len(fractional) == 0: print('Found feasible solution - objective %g' % model.ObjVal) break # Fix the first quartile to the nearest integer value nfix = max(int(len(fractional)/4), 1) for i in range(nfix): v = fractional[i] fixval = int(v.X+0.5) v.LB = fixval v.UB = fixval print(' Fix %s to %g (rel %g)' % (v.VarName, fixval, v.X)) model.optimize() # Check optimization result if model.Status != GRB.OPTIMAL: print('Relaxation is infeasible') break
