fixanddive.py

#!/usr/bin/env python3.9

# Copyright 2022, 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.

import sys
import gurobipy as gp
from gurobipy import GRB


# Key function used to sort variables based on relaxation fractionality

def sortkey(v1):
    sol = v1.X
    return 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