Big M method for continuous variables and cvx precision

#1

Let p_{i,j} \in \mathbb{R}_{\geq 0}, for i=1,\dots, n, j=1, \dots, m. As one of the constraints of my problem, I am looking for h such that

g_i(h) := \sum_{j=1}^h p_{i,j} < 1.

To find h, I defined a_{i,j} \in \{0,1\} such that

a_{i,h} = \begin{cases} 1 \qquad \text{if } g_i(h) < 1 \quad h=1, \dots, m, \\ 0 \qquad \text{otherwise}. \end{cases}

To implement the if condition above, I used the big-M method as

\begin{align} g_i(h)& \geq 1 - M a_{i,h} \\ 1&> g_i(h) - M(1-a_{i,h} ) . \end{align}

The problem is that the big-M method works well for ILPs while the variable, here the $p$s, are non-integer. When g_i(h) is very close to 1, I do not get the correct value for h.
I tried it out with different precision levels of CVX but it did not help either.

I was wondering if there is a trick for this in CVX.

(Mark L. Stone) #2

I’m not sure whether you are trying to model a strict linear inequality constraint, or a conditional (logical) constraint. Either way, you will have to address the matter of solver feasibility tolerance.

CVX treats and sends to the solver all < constraints as <=. In order to get strict inequality, you will need to introduce a small positive number, small_number. Then use the constraint
sum(p(i,:),2) + small_number <= 1 .

In order to allow small_number to be as small as possible, while still dealing with solver tolerance, you will need to adjust the solver feasibility tolerance (applicable to linear (inequality) constraints) from its default value. Do this using cvx_solver_settings( '{name}', {value} ) . See http://cvxr.com/cvx/doc/solver.html#advanced-solver-settings . You will need to examine the solver documentation to determine the parameter name to adjust.

I believe that cvx_precision controls solver termination criteria, but not solver feasibility tolerance, which I believe is is what you need to adjust.

#3

Great! It worked out. I am using Gurobi, so I set a small value for ‘FeasibilityTol’.
Many thanks Mark.