Possible to reduce problem to linear problem?

56 Views Asked by At

I've been trying my hand at using the Google OR Tools (GLOP) solver, and I've successfully modeled all needed constraints save for one.

Given an array of rational numbers, p of length n. I want to define a constraint so that

$$ \forall i\in [1,n-2]: f(p_i) + f(p_{i+1}) + f(p_{i+2}) \leq 2 $$

where

$$ f(x) = \begin{cases}0 & \text{for } x = 0 \\1 & \text{for } x \gt 0 \\\end{cases} $$

In words: I want to constrain the values of p so that at most two consecutive elements are greater than zero.

Can this problem be reduced to or approximated as a linear problem? And if not, how would you solve it?

var solver = Solver.CreateSolver("GLOP");
var p = solver.MakeNumVarArray(n, 0, 1);

EDIT: For sake of context, the objective is defined as:

var objective = solver.Objective();
for(var i = 0; i < n; i++)
    objective.SetCoefficient(p[i], prices[i]);
objective.SetMaximization();
1

There are 1 best solutions below

1
On BEST ANSWER

Let $M_i$ be a (small) constant upper bound on $p_i$. Introduce binary variables $y_i$ and linear constraints: \begin{align} y_i + y_{i+1} + y_{i+2} &\le 2 &&\text{for $i\in\{1,\dots,n-2\}$} \\ p_i &\le M_i y_i &&\text{for $i\in\{1,\dots,n\}$} \\ \end{align}