Optimizing Part of the Objective Function II

Today's post extends yesterday's entry about optimizing a portion of the original objective function. I won't repeat much of the previous post, to save myself some typing.

The actual question motivating these posts, which I originally misread, asked how to minimize, not maximize, the sum of the $K$ largest terms in $\sum_{i=1}^N x_i$ (where $x$ is a vector of decision variables in an optimization model). As I mentioned in the last outing, that (or the symmetric case, maximizing the sum of the $K$ smallest terms), is trickier than what I covered yesterday. Everything from yesterday's post (the introduction of binary variables $z_i$ and auxiliary variables $y_i$ and the added constraints) carries over, with one exception: the objective function is now$$\textrm{minimize} \sum_{i=1}^N y_i.$$On top of all that, we require some additional constraints.

Update

Forget everything that follows and just skip down to the comments section. There's a clever reformulation, posted by Michael Grant in a comment, that gets the job done with a linear number of new variables (all continuous) and a linear number of constraints. I knew another formulation with no integer variables, and in fact only one new variable at all, but with an exponential number of constraints. I was debating whether to post it until I saw the more efficient solution in Michael's comment.

5. Lower bounds on auxiliary variables

If we do not do something to prevent it, the solver will achieve an ideal objective value of 0 by setting $y_i = 0$ regardless of whether $z_i$ is 0 or 1. So we need additional constraints to ensure that $z_i = 1 \implies y_i = x_i$. We can accomplish that with$$y_i \ge x_i - U_i(1 - z_i)\quad \forall i \in \{1,\dots,N\},$$which forces $y_i\ge x_i$ if $z_i = 1$ and is vacuous if $z_i = 0$.

6. Choosing the $K$ largest terms

Choosing the largest of the $x_i$ was automatic when the objective was to maximize the sum. When the objective is minimization, the solver will "want" to choose the smallest of the $x_i$, and we need to constrain it to select the largest values. An easy way to do this is to note that choosing the $K$ largest values is equivalent to saying that every value chosen is at least as big as every value not chosen. Expressed mathematically,$$z_i = 1 \bigwedge z_j = 0 \implies x_i \ge x_j.$$Note that, having assumed $0\le x_k \le U_k\,\forall k$, the most negative that any difference $x_i - x_j$ could be would be $0 - U_j = -U_j$. That leads to the following additional constraints:$$x_i - x_j \ge -U_j(1-z_i+z_j)\quad \forall i,j\in \{1,\dots,N\},\,i\neq j.$$
Coupled with yesterday's formulation, that should get the job done.

Optimizing Part of the Objective Function

A somewhat curious question showed up on a forum today. The author of the question has an optimization model (I'll assume it is either a linear program or mixed integer linear program) of the form \begin{alignat*}{2} & \textrm{maximize} & & \sum_{i=1}^{N}x_{i}\\ & \textrm{s.t.} & & x\in\mathcal{X} \end{alignat*} where the feasible region $\mathcal{X}$ is presumably polyhedral. What the author wants to do is instead maximize the sum of the $K$ largest terms in the objective, for some fixed $K<N$. The question was how to do this.

In effect, the author wants to selectively turn some terms on and others off in the objective function. Any time I think about turning things on and off, I immediately think of using binary variables as the "switches". That in turn suggests the likely need for auxiliary variables and the very likely need for a priori bounds on the things being turned on and off. Here is one solution, step by step, assuming that the $x$ variables are nonnegative and that we know a finite upper bound $U_i$ for each $x_i$.

1. Introduce a binary variable for each term to be switched on/off.

So we add variables $z_i \in \{0,1\}$ for $i\in 1\dots N$, with $z_i=1$ if and only if $x_i$ is to be counted.

2. Limit the number of terms to count.

This is just the constraint $$\sum_{i=1}^N z_i = K$$ (with the option to change the equality to $\le$ if you want up to $K$ terms counted.

3. Replace the objective terms with surrogates that can be turned on/off.

We will add real variables $y_1,\dots,y_N$ and make the objective $$\textrm{maximize} \sum_{i=1}^N y_i.$$

4. Connect the surrogate variables to the original variables and the on-off decisions.

Here we benefit from a key property: if we limit the objective function to $K$ terms, the fact that we are maximizing will naturally favor the $K$ largest terms. So we just need the following constraints: \begin{alignat*}{2} y_{i} & \le x_{i} & & \forall i\in\left\{ 1,\dots,N\right\} \\ y_{i} & \le U_{i}z_{i} & \quad & \forall i\in\left\{ 1,\dots,N\right\} . \end{alignat*}If $z_i = 0$, the second constraint will force $y_i=0$ and the term will not contribute to the objective function. If $z_i=1$, the second constraint will become vacuous and the first term will allow $y_i$ to contribute an amount up to $x_i$ to the objective. Since the objective is being maximized, $y_i=x_i$ is certain to occur.

A symmetric version of this will work to minimize the sum of the $K$ smallest terms in the objective. Minimizing the sum of the largest terms or maximizing the sum of the smallest terms is a bit trickier, requiring some extra constraints to enforce $y_i=x_i$ when $z_i = 1$. Oops! It's actually easier, as pointed out in a comment in my next post.

More Shiny Hacks

In a previous entry, I posted code for hack I came up with to add vertical scrolling to the sidebar of a web-based application I'm developing in Shiny (using shinydashboard). Since then, I've bumped into two more issues, leading to two more hacks that I'll describe here.

First, I should point out that I'm using the DT 0.1, shiny 0.12.1 and shinydashboard 0.5.0 packages. DT provides an interface to the DataTables JavaScript library, which handles rendering and processing of the table in the browser. Future updates to any of them could make these hacks (and previous one) unnecessary, or could just as easily break them. I also want to emphasize that these are true kludges, not to be held up as examples of good programming practice.

The main body of my application uses tabs, and on one of the tabs I expose a data frame  (read only) using DT::dataTableOutput() in the user interface file and DT::renderDataTable() in the server file. The application allows the user to restrict which rows are displayed by setting filters on one or more columns, implemented by adding the option filter = "top" to the invocation of renderDataTable(). Clicking in a filter box expands the box by placing either a double slider (for numeric columns) or a selectize control (for text columns) beneath the box. This will prove to be significant.

Problem 1: Horizontal Scrolling

In some cases, the data frame will be too wide to fit on one screen. Adding the option scrollX = TRUE to renderDataTable() causes DataTables to add a horizontal scroll bar to the table when needed. According to the documentation for the DT package (the note at the end of section 2.7),

"The position of column filters may be off when scrolling is enabled in the table, e.g. via the options scrollX and/or scrollY."

Sure enough, if the scrollX option is turned on, the table fails to adjust its vertical spacing properly when the user clicks in a column filter control. As a result, only a very small sliver from the top of the selectize or double slider control is visible, making input nigh unto impossible. This happens whether the filter controls are positioned at the top or bottom of the table.

The best solution I could come up with was to omit scrollX = TRUE, which lets the filters behave properly. That leaves the matter of those wide tables to resolve. My solution was to hack the CSS for the user interface. In the earlier post, I showed the CSS hack to get vertical scrolling in the sidebar, adding the following to the .ui file:

  dashboardSidebar(
    tags$head(
      tags$style(HTML("
                      .sidebar { height: 90vh; overflow-y: auto; }
                      " )
      )
    ),
    ...

To add horizontal scrolling to the data table, when needed, I just add one more line:

  dashboardSidebar(
    tags$head(
      tags$style(HTML("
                      .sidebar { height: 90vh; overflow-y: auto; }
                      .dataTables_wrapper { overflow-x: scroll; }
                      " )
      )
    ),
    ...

So far, that seems to work.

Problem 2: Undoing a Row Sort

To allow the user to sort the data by one or more columns, I added the following options to renderDataTable():

      extensions = c('ColVis', 'ColReorder'),
      options = list(dom = 'C<"clear">Rlfrtip',
                     colReorder = list(realtime = TRUE))

(The ColVis extension adds a button to let the user select which columns to display, and has nothing to do with the problem at hand.) With the ColReorder extension installed, clicking repeatedly on a column heading toggles between ascending and descending sorts using that column. (Shift-clicking other column headings invokes secondary, tertiary etc. orderings).

That's handy, but what if the user wants to go back to the original ordering? In earlier versions of the DataTables library, clicking a heading cycled through ascending order, descending order and no sort. According to the discussion here, that last option was unintended by the author of DataTables, and he removed it in a recent version. As I read the discussion, it may come back in some future version, but for now it's gone. There are alternative mechanisms to undo the sort, but they currently require a separate control to activate them. As Yihui Xie, the developer of the DT package, points out:

"It will be awkward to provide a separate button such as Remove Sorting in the UI that does this job."

It may help to start with a screen shot of a typical table, before applying the hack. The data comes from the USArrests data set in the datasets package.

Data table before the hack

I clicked on the "Murder" column, and then shift-clicked the "NA." (state name) column twice, to sort by ascending murder rate, breaking ties in reverse alphabetical order by state. Note the row numbers on the left and, significantly, the lack of an option to sort on them. In this particular case, the data comes in alphabetical order by state, so sorting on the state column would restore the original order. Other data sets may not come with the data ordered according to any of the variables, so that is not a viable option in general.

My hack is to turn the row indices into a sortable column of data. First, I need to remove the exiting column, which turns out to be the row names of the data frame. In the USArrests data frame, the state names are the row names, but this copy was pulled from a table in an Excel spreadsheet, where the state names were interpreted as a column of data without a column heading (hence the automatically supplied "NA." heading). Since that left the data frame without row names, a default set of names (the row numbers) were automatically supplied.

Removing the row names is easy: add the option rownames = FALSE to the call to renderDataTable(). The next step is to add a column of row indices to the data set. In the server portion of my code, there is a function that lets the user specify an input file and then reads the data into a data frame named x. Adding the line

x <- cbind("(index)" = 1:nrow(x), x)

creates an additional column, with the unconventional (but legal) name "(index)". The column name was chosen in part to make it unlikely that it will collide with an actual column heading. The new column will automatically be given a sort control, as shown in the next screen shot:

Data table (sorted) after hack

Clicking on the "(index)" column sorts the data into its original order:

Data table in original order

Clicking again sorts it into the reverse of the original order, although I do not see that as a particularly useful option.

Note: All syntax highlighting in this post was created by Pretty R at inside-R.org.