Tuesday, February 19, 2013

Counting Initial Zeros

Suppose, in a mathematical program, I have $n$ binary variables arranged in a vector ($x\in \{0,1\}^n$), and I want an integer variable $z\in \mathbb{Z}$ to equal the number of initial zeros in $x$. If $x=0$ I want $z=n$, if $x=(1,\dots)$ I want $z=0$, if $x=(0,0,0,1,\dots)$ I want $z=3$, and so on. It turns out I can do this with $2n$ additional constraints and no additional decision variables. (Programming note: I'm using mathematical notation, i.e., one-based indexing. If you are coding in a language with zero-based indexing, such as C++ or Java, keep an eye out for adjustments.)

The following two sets of constraints do the job:

\begin{eqnarray*} z & \le & n-(n-k+1)x_{k},\: k=1,\dots,n\\ z & \ge & k-n\sum_{j=1}^{k}x_{j},\: k=1,\dots,n. \end{eqnarray*}
The proof is left to the reader as an exercise. The first set of constraints will be unnecessary if overestimating the count would hurt the model's objective value; the second set is unnecessary if underestimating the count would hurt the model's objective value.

I make no claim that this is the best formulation, just that it works. The first set of constraints is sparse but the second set unfortunately is not, so hopefully this would not need to be done a large number of times in the model.

Minor tweaks to this approach will allow you to count the number of initial ones rather than zeros, or find the index of the first one in $x$ (assuming $x\neq 0$).

2 comments:

  1. Hi Paul,

    nice post! Reminds me of a post at "Yet Another Math Programming Consultant" on Sorting by MIP. Similarly to that setting, you can use the objective function to guide the selection of z (and then drop the second constraint). It suffices to make the objective coefficient c_z of z very small so that it does not "disturb" the normal objective function. In case of a minimization problem, choose c_z < 0, for a maximization problem choose c_z > 0.

    Best,
    Michael

    ReplyDelete
    Replies
    1. Michael,

      There is a similarity to the sorting problem (and I like your model for the latter!). The catch here is that the count variable z most likely appears in other constraints of the model (else why bother with it?), possibly in such a way that an understated count allows a "solution" that inflates (deflates) the objective value of the rest of the solution if maximizing (minimizing). So adding a penalty for understatement to the objective function might not be sufficient, unless the penalty were stiff (in which case it might "disturb" the objective function enough to lead to a suboptimal solution of the original problem).

      Thanks for the comment,
      Paul

      Delete

If this is your first time commenting on the blog, please read the Ground Rules for Comments. In particular, if you want to ask an operations research-related question not relevant to this post, consider asking it on OR-Exchange.