Linearizing the product of a binary and a continuous variable

Question

I have an MIP optimization problem that has a constraint $p\geq xy$, where $x$ is a binary variable, $p$ and $y$ are non-negative continuous variables.

I tried the Big-M method. However, the upper bound for $y$ is quite large ($M \geq 10^{15}$). All the MIP solver I tried have numerical problems and cannot solve the problem correctly. I tried to set the solver parameters and the numerical problem still exists.

Since the value range of $y$ is from $10^{-5}$ to $10^{14}$, it seems the values cannot be scaled directly in the problem.

Is there any other way to linearize the product $xy$ which can avoid numerical problems?

Answer 1

Some solvers allow you to directly express indicator constraints $x=1 \implies p \ge y$. Behind the scenes the solver might introduce big-M constraints or might branch on the indicator constraints. In the latter case, the constraint is ignored in the root node linear programming relaxation (weakening the relaxation but avoiding numerical difficulties from big-M); if the constraint is violated (that is, if $x=1$ and $p < y$), the $x=1$ branch imposes linear constraint $p \ge y$.

Alternatively, if you have only one such constraint, just solve two problems, effectively doing this branching yourself.

Answer 2

As Rob Pratt suggested, if you have one binary variable, you can just solve two problems. If you have a few (say $n$) binary variables, and $2^n$ is small, you can just solve a problem for each combination.

If that's impractical, you might look at combinatorial Benders decomposition [1]. You put $x$ and any other integer variables in the master problem; $p$, $y$ and any other continuous variables go in the subproblem. Given a feasible solution $\hat{x}$ to the master problem, you include the constraint $p\ge y$ if $\hat{x}=1$ and omit the constraint if $\hat{x}=0$. If the subproblem is feasible and its optimal value matches the claimed objective component in the master, accept the master solution. Otherwise, generate either a Benders optimality cut or a Benders feasibility cut. The cuts are similar but not identical to the cuts you get in conventional Benders decomposition. The advantage of the combinatorial Benders approach is that you do not need a constant $M$. The disadvantage is that, as an outer approximation approach, Benders may be slower than solving a single MIP model ... but that apparently is not an issue, since your minimal valid $M$ triggers numerical problems.

[1] Codato, G. & Fischetti, M. Combinatorial Benders' Cuts for Mixed-Integer Linear Programming. Operations Research, 2006, 54, 756-766.