2

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

Kuifje
  • 13,324
  • 1
  • 23
  • 56
Hussein Sharadga
  • 409
  • 1
  • 10

3 Answers3

8

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}

RobPratt
  • 32,006
  • 1
  • 44
  • 84
  • 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? – Hussein Sharadga Dec 01 '22 at 21:05
  • 1
    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. – RobPratt Dec 01 '22 at 21:18
  • Thank you! @ RobPartt. The PORTA formulation you suggested might be the best as it requires fewer constraints than all other formulations. – Hussein Sharadga Dec 04 '22 at 00:12
  • 1
    More importantly, the PORTA formulation yields the integer hull, so there are no fractional extreme points. – RobPratt Dec 04 '22 at 00:19
7

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

RobPratt
  • 32,006
  • 1
  • 44
  • 84
xd y
  • 1,186
  • 3
  • 9
  • 1
    +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. – RobPratt Dec 01 '22 at 15:05
  • 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. – Hussein Sharadga Dec 02 '22 at 03:04
  • 1
    Yes but I just found the last constraint in the second formulation is stupid and could be replaced by $\sum y_i \leq 1$... – xd y Dec 02 '22 at 03:13
  • Thanks, @ xd y. It could be replaced, but both solve the problem. Thank you so much for your help! – Hussein Sharadga Dec 03 '22 at 23:00
2

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$

Sutanu Majumdar
  • 3,461
  • 1
  • 2
  • 11
  • Thanks! Sutanu. I believe that your first two constraints contradict each other. – Hussein Sharadga Dec 01 '22 at 22:27
  • 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. – Sutanu Majumdar Dec 01 '22 at 22:32
  • The following is not working: 
    import numpy as np
m=gp.Model()
cost=[-70,-60,-50,-40,-30,-20,-10,0]
cost=np.flipud(cost)
x=[1,0,0,1,0,1,0,0]
x=np.flipud(x)
# x=[0,0,0,0,0,0,0]
M=10
C=1
B=m.addVars(len(x), vtype=GRB.BINARY)
obj=gp.quicksum(cost[i]*B[i] for i in range (len(x)))
m.setObjective(obj)




m.addConstrs(M*B[i]>=C-x[i] for i in range(len(x)))
m.addConstrs(M*B[i]>=x[i]-C for i in range(len(x)))


for i in range(len(x)): 
    j=i-1

    m.addConstr(gp.quicksum(B[jj] for jj in range (j))<=i)

m.optimize()
    – Hussein Sharadga Dec 02 '22 at 00:32
  • 1
    Let me get back to you. – Sutanu Majumdar Dec 02 '22 at 01:48
  • 1
    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 – Sutanu Majumdar Dec 02 '22 at 03:47
  • Thanks. For "I don't think 1 is there in the array". 1 is in the array, the array is x. x=[1,0,0,1,0,1,0,0]. "Also you are trying to determine first index for C=1 in the array, x?" yes. – Hussein Sharadga Dec 03 '22 at 01:04
  • 1
    Ok my bad, I thought you are comparing with cost. – Sutanu Majumdar Dec 03 '22 at 01:29
  • Thank you so much for your effort to help. I do appreciate your time! – Hussein Sharadga Dec 03 '22 at 02:14