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.
© 2001-2019 Fair Isaac Corporation. All rights reserved. This documentation is the property of Fair Isaac Corporation (“FICO”). Receipt or possession of this documentation does not convey rights to disclose, reproduce, make derivative works, use, or allow others to use it except solely for internal evaluation purposes to determine whether to purchase a license to the software described in this documentation, or as otherwise set forth in a written software license agreement between you and FICO (or a FICO affiliate). Use of this documentation and the software described in it must conform strictly to the foregoing permitted uses, and no other use is permitted.