2
$\begingroup$

How to formulate this problem as MIP:

For example, we have the following vector of binary variables: $$ x= [0, 0, 0, 1, 0, 1, 1] $$ How to find out when the first "1" is recorded? For example, the index of the first "1" is 4. How to let the solver return for example, $y =[0, 0, 0, 1, 0, 0, 0].$

Improve this question
$\endgroup$

3 Answers 3

Reset to default
8
$\begingroup$

Here's a formulation if at least one $x_i$ must be $1$: \begin{align} \sum_i y_i &= 1 \tag1\label1\\ y_i &\le x_i &&\text{for all $i$} \tag2\label2\\ y_i &\le 1-x_j &&\text{for $j<i$} \tag3\label3 \end{align} Constraint \eqref{1} selects exactly one $y_i$ to be $1$. Constraint \eqref{2} enforces the implication $y_i \implies x_i$. Constraint \eqref{3} enforces the implication $y_i \implies \lnot x_j$.

If instead it is possible that $x_i=0$ for all $i$, relax \eqref{1} to $\le 1$ and impose \begin{align} y_i &\ge x_i - \sum_{j<i} x_j &&\text{for all $i$} \tag4 \end{align}

In either case, you can use \eqref{1} to strengthen \eqref{3} as follows: \begin{align} \sum_{i>j} y_i &\le 1-x_j &&\text{for all $j$} \tag5 \end{align}

See How can I strengthen a family of constraints in the presence of a clique constraint?

For the general case where $x \equiv 0$ is feasible, PORTA yields the following formulation: \begin{align} \sum_i y_i &\le 1 \\ y_i &\le x_i &&\text{for all $i$} \\ x_i &\le \sum_{j \le i} y_j &&\text{for all $i$} \end{align}

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thank you so much. Constraints 1-3 solve the problem. Yes, it is possible that $xi=0$ for all $i$. In that case, I believe you mean replacing constraint 1 with constraint 4 and constraint 3 with constraint 5. I mean, solve the problem with constraints 2, 4, and 5. That also solves the problem in less computation time since it reduces the number of constraints! I am wondering what you mean by " strengthen." Do you mean reducing the number of constraints? $\endgroup$
    – Hussein Sharadga
    Commented Dec 1, 2022 at 21:05
  • 1
    $\begingroup$ If you impose $(2)$, $(4)$, and $(5)$, you can omit $(1)$, which is dominated by $(5)$, and you end up with the second formulation by @xdy. By strengthen, I mean that the LP feasible region is smaller, cutting off more fractional solutions. $\endgroup$
    – RobPratt
    Commented Dec 1, 2022 at 21:18
  • $\begingroup$ Thank you! @ RobPartt. The PORTA formulation you suggested might be the best as it requires fewer constraints than all other formulations. $\endgroup$
    – Hussein Sharadga
    Commented Dec 4, 2022 at 0:12
  • 1
    $\begingroup$ More importantly, the PORTA formulation yields the integer hull, so there are no fractional extreme points. $\endgroup$
    – RobPratt
    Commented Dec 4, 2022 at 0:19
7
$\begingroup$

Suppose the index is 1-based and set constant $u_0 = 0$. With binary variables $u_i, y_i, i=1,\dots,n$ and constraints $$ \begin{align} u_i &\geq x_i\\ u_i &\geq u_{i-1}\\ u_i &\leq x_i + u_{i-1}\\ y_i &\leq u_i\\ y_i &\leq 1 - u_{i-1}\\ y_i &\geq u_i - u_{i-1} \end{align} $$ $y_i$ indicate the first $x$.

In logic expressions: $$ u_i = x_i \vee u_{i-1}\\ y_i = u_i \wedge \neg u_{i-1} $$

It is just my first thought and I have no idea if it is efficient.

Second formulation: $$ y_i \leq x_i\\ y_i \geq x_i - \sum_{i' < i} x_{i'}\\ y_i \leq 1 - \sum_{i' < i} y_{i'} $$

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ +1. We had similar ideas for your second formulation. I suspect that your first formulation will scale better, with only $O(n)$ constraints, each of which is sparse. $\endgroup$
    – RobPratt
    Commented Dec 1, 2022 at 15:05
  • $\begingroup$ Thanks! Both formulations work. As @ RobPratt mentioned, the second formulation is expected to be better as it has less number of constraints and binary variables. $\endgroup$
    – Hussein Sharadga
    Commented Dec 2, 2022 at 3:04
  • 1
    $\begingroup$ Yes but I just found the last constraint in the second formulation is stupid and could be replaced by $\sum y_i \leq 1$... $\endgroup$
    – xd y
    Commented Dec 2, 2022 at 3:13
  • $\begingroup$ Thanks, @ xd y. It could be replaced, but both solve the problem. Thank you so much for your help! $\endgroup$
    – Hussein Sharadga
    Commented Dec 3, 2022 at 23:00
2
$\begingroup$

If number is non-binary, say non negative continuous number $c$, introduce a vector of binary $y_i$ initialized to 0.
Have two binary variables $z_1 \ and z_2$

$c - x_i \le My_{i}$
$x_i - c \le M(1-y_{i})$
$\sum_{j \lt i} y_j \le i \quad \forall i \in\ N$
$y_{i+1}\le y_i \ \forall i \in\ N$: this ensures y turns 0 once c=x and remains 0 for rest of the array.

First index will be $\sum_{j \lt i} y_j$

Improve this answer
$\endgroup$
8
  • $\begingroup$ Thanks! Sutanu. I believe that your first two constraints contradict each other. $\endgroup$
    – Hussein Sharadga
    Commented Dec 1, 2022 at 22:27
  • $\begingroup$ if $c-x_i > 0$ then $y_i$ has to be 1, then $x_i-c <0, y_i$ is free to be 1. Vice-versa, in other words if $c \neq x_i$ y is 1. When $c=x_i$ then possible $y_i = 0$, that will be forced by last constraint. $\endgroup$
    – Sutanu Majumdar
    Commented Dec 1, 2022 at 22:32
  • 1
    $\begingroup$ Let me get back to you. $\endgroup$
    – Sutanu Majumdar
    Commented Dec 2, 2022 at 1:48
  • 1
    $\begingroup$ Obj should be =gp.quicksum(B[i] for i in range (len(x))) or simple B.sum(). Also you are trying to determine first index for C=1 in the array, x. I don't think 1 is there in the array. I have added one more constraint B[i+1]<=B[i] for i in range(len(x))-1 $\endgroup$
    – Sutanu Majumdar
    Commented Dec 2, 2022 at 3:47
  • 1
    $\begingroup$ Ok my bad, I thought you are comparing with cost. $\endgroup$
    – Sutanu Majumdar
    Commented Dec 3, 2022 at 1:29

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