# What is a good way to penalise LP relaxation?

I have a binary integer program. It is of a large size and the solver is taking longer time.

I am thinking of relaxing the binary integer variable and making it a continuous variable.

How can I penalise the objective function?

• Penalize the objective function? Do you mean how you an add a some kind of penalty to the objective to make the continuous relaxation closer to the original problem? Jun 3 at 12:29
• @JohanLöfberg, yes. Jun 3 at 14:01
• This depends on where the solver is stuck. Could you maybe post a log file of a run so that we can see what the situation is? Depending on this various techniques (relaxations, heuristics etc.) may become apparent. Jun 4 at 7:48

You can't quite create a penalty function to enforce integrality and keep your problem linear, at best it would be quadratic (which could indeed be easier to solve sometimes).

The closest thing that comes to mind along the lines of what you propose is to create a feasibility pump objective:

$$\min \bar f(x)+\Delta(x,\tilde x)$$ s.t. your relaxed constraints, where:

$$\Delta(x,\tilde x) = \sum_{j\in I:\tilde x = 1}(1-x_j)+\sum_{j\in I:\tilde x = 0}(x_j)$$

and $$\bar f(x)$$ is your relaxed objective and $$I$$ is the set of your binary variables.

This does not guarantee a global solution, but it could find an integer feasible point.

This is then solved in a loop where we solve the relaxed LP and feed that into the pump objective (that's where the $$\tilde x$$ comes from).

Just a heads up though - if you're using CPLEX/GUROBI you probably shouldn't bother trying it, as their heuristics are much better than this.

• thanks. Would would please elaborate on $\Delta(x,\tilde{x})$. Jun 4 at 0:08
• Yes, I am using CPLEX. You mentioned that $I$ is the set of binary variables. But in LP relation, I define them as continuous variables! Why/How do we have a set of binary variables then? Jun 4 at 0:11
• It is the set of binary variables in your original problem. Even if you relax it, they will still be there, but will now be continuous. What this is doing is basically solving an LP that encourages the variables that were integral in the LP solution you feed in to remain integral, and hope you can force a few more to integrality per iteration, update the penalty function by changing the objective to include the new 0/1 variables, and repeat. It's not a good solution, but it's the closest to what you asked in terms of using a penalty function. Jun 4 at 11:42