2
$\begingroup$

In a much larger MINLP problem, I have set of variables $\{a_{ij}\}_{m,n}$, such that $0 \leq a_{ij} \leq 1 $ for all $i$, $j$, which I could think of as a matrix, for which I have two requirements:

  • there is exactly one non-zero element per row;
  • there is at most one non-zero element per column.

This can easily be achieved by letting $a_{ij} = x_{ij}\,b_{ij}$ and:

\begin{align*} &\min f(x_{ij}\,b_{ij},\ldots)\\ &\mbox{s.t.}\\ &\sum_j x_{ij}\,b_{ij} = 1\quad \forall i,\\ &\sum_i x_{ij}\,b_{ij} \leq 1\quad \forall j,\\ &\vdots\\ &x_{ij} \in \{0,1\}, \ 0 \leq b_{ij} \leq 1\quad \forall i,j. \end{align*} ( $f$ is some non-linear function in multiple variables, and constraints not relevant for this question are omitted)

However, for computational reason, I'd prefer to do without all those extra binary variables $x_{ij}$. That is, I am looking for a formulation of the constraints without introducing extra binary variables.

Is there a way to construct linear constraints on the $a_{ij}$, that ensure that the two requirements (as mentioned on the top of this post) are satisfied?

Any suggestions are much appreciated.

$\endgroup$
4
$\begingroup$

No, this is not possible. There is a standard way of showing this:

The feasible region of your constraints is not convex. For example, $x_{1,1}=1$, $x_{1,2}=0$ is feasible, $x_{1,1}=0$, $x_{1,2}=1$ is feasible, but the midpoint $x_{1,1}=1/2$, $x_{1,2}=1/2$ is not feasible.

The feasible set of a system of linear equality and inequality constraints is always convex.

Thus your desired constraint can’t be expressed with linear constraints.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.