#!/usr/bin/env python3# Copyright 2025, Gurobi Optimization, LLC# Implement a simple MIP heuristic.  Relax the model,# sort variables based on fractionality, and fix the 25% of# the fractional variables that are closest to integer variables.# Repeat until either the relaxation is integer feasible or# linearly infeasible.importsysimportgurobipyasgpfromgurobipyimportGRB# Key function used to sort variables based on relaxation fractionalitydefsortkey(v1):sol=v1.Xreturnabs(sol-int(sol+0.5))iflen(sys.argv)<2:print("Usage: fixanddive.py filename")sys.exit(0)# Read modelmodel=gp.read(sys.argv[1])# Collect integer variables and relax themintvars=[]forvinmodel.getVars():ifv.VType!=GRB.CONTINUOUS:intvars+=[v]v.VType=GRB.CONTINUOUSmodel.Params.OutputFlag=0model.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.foriterinrange(1000):# create a list of fractional variables, sorted in order of increasing# distance from the relaxation solution to the nearest integer valuefractional=[]forvinintvars:sol=v.Xifabs(sol-int(sol+0.5))>1e-5:fractional+=[v]fractional.sort(key=sortkey)print(f"Iteration{iter}, obj{model.ObjVal:g}, fractional{len(fractional)}")iflen(fractional)==0:print(f"Found feasible solution - objective{model.ObjVal:g}")break# Fix the first quartile to the nearest integer valuenfix=max(int(len(fractional)/4),1)foriinrange(nfix):v=fractional[i]fixval=int(v.X+0.5)v.LB=fixvalv.UB=fixvalprint(f"  Fix{v.VarName} to{fixval:g} (rel{v.X:g})")model.optimize()# Check optimization resultifmodel.Status!=GRB.OPTIMAL:print("Relaxation is infeasible")break