Fixing binary variables in an Binary Integer Program

Question

I have a Binary Integer Program with two binary decision variables and additionally have an expected solution. At the time of execution of this program I expect the parameters to change slightly. I am using the expected solution to fix the values of the decision variables according to it and utilize the model to compute the rest of the decisions at time of execution. I was curious whether this approach benefits the program in some way assuming most of the variables are fixed from the expected solution. Is there an alternative approach that is better?

Answer 1

Actually, it effectively depends on the problem you have at hand. Modern solvers have often been armed with dozen of (SOTA) heuristics, cutting plane approaches, powerful pre-solving phases, etc. Also, to inject a heuristic solution usually, there are two ways. First, by something like a MIP-Start, and the second by using the heuristic callback if the solver supports that. In many cases, there might be a situation in which the founded heuristic solution would be rejected by the solver process. By Googling or searching the community you definitely could find many useful notes. (e.g. this).

As a simple example, you can check the behavior of the solver again with a founded heuristic solution. Suppose, there is a bin-packing problem only with two items and one bin. (this is a tiny example that can be illustrated). The feasible solution of the problem is:

and the optimal solution, objective function, would be equal to one. (it is obviously!). Now, I am trying to inject a heuristic solution $\{1,1,0\}$. The solver's log shows that:

Processing 1 MIP starts.
MIP start 'm1' defined no solution.
Warning:  No solution found from 1 MIP starts.
Retaining values of one MIP start for possible repair.
Found incumbent of value 1.000000 after 0.00 sec.

and as the second try inject the solution $\{0,1,1\}$. Then the log file again shows:

Processing 1 MIP starts.
MIP start 'm1' defined solution with objective 1.0000.
1 of 1 MIP starts provided solutions.
MIP start 'm1' defined initial solution with objective 1.0000.
MIP emphasis: optimality.
MIP search method: dynamic search.
Parallel mode: none, using 1 thread.
Root relaxation solution time = 0.00 sec.

Once a wise man said to check a heuristic solution that obtained from an external program/function, it would be worth fixing the problem variables at this solution and investigating if it can provide at least a feasible solution. I hope it helps.

Answer 2

There are approaches like this, kind of heuristic you may say, where you can fix values of some variables like a warm start and allow the solver to start search from the given feasible candidate solution.
Other than that there's pre-solving and introduction of cuts/constraints like knapsack cover. Such techniques are followed for solving MILP models.
FICO has described one such heuristic where you start by solving LP relaxation, then fixing values of some of the binaries and then iteratively solvng the MILP using the best candidate solution as the bounds.