Binary variable fixing heuristic
The heuristic we wish to implement should perform the following steps:
- Solve the LP relaxation and save the basis of the optimal solution
- Rounding heuristic: Fix all variables `buy' to 0 if the corresponding fraction bought is close to 0, and to 1 if it has a relatively large value.
- Solve the resulting MIP problem.
- If an integer feasible solution was found, save the value of the best solution.
- Restore the original problem by resetting all variables to their original bounds, and load the saved basis.
- Solve the original MIP problem, using the heuristic solution as cutoff value.
Step 2: Since the fraction variables frac have an upper bound of 0.3, as a `relatively large value' in this case we may choose 0.2. In other applications, for binary variables a more suitable choice may be 1-ε, where ε is a very small value such as 10-5.
Step 6: Setting a cutoff value means that we only search for solutions that are better than this value. If the LP relaxation of a node is worse than this value it gets cut off, because this node and its descendants can only lead to integer feasible solutions that are even worse than the LP relaxation.