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].$

$\endgroup$

3 Answers 3

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}

$\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$ 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
    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$ 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
    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'} $$

$\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
    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$ 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
    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$ 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$

$\endgroup$
8
  • $\begingroup$ Thanks! Sutanu. I believe that your first two constraints contradict each other. $\endgroup$ 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$ Dec 1, 2022 at 22:32
  • 1
    $\begingroup$ Let me get back to you. $\endgroup$ 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$ Dec 2, 2022 at 3:47
  • 1
    $\begingroup$ Ok my bad, I thought you are comparing with cost. $\endgroup$ Dec 3, 2022 at 1:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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