Selecting Dispersed Points

Fellow blogger Erwin Kalvelagen posted a comparison of two binary programming models, one quadratically constrained and one linearly constrained, for the problem of selecting a maximal number of points from a finite set subject to the requirement that no two selected points be closer than a specified distance. The models were an answer to a question posted on Computational Science Stack Exchange. Not surprisingly, the linearized version tended to solve faster than the quadratic version.

In Erwin's linear model, the constraints take the form $$\underline{D}(x_i + x_j - 1) \le d_{i,j} \quad (1)$$ where $d_{i,j}$ is the distance between points $i$ and $j$, $\underline{D}$ is the minimum allowable distance between selected points, and $x_k$ is a binary variable indicating whether point $k$ is selected (1) or not (0). I coded both his models in Java, using CPLEX 22.1.1, along with another linear model where the constraints are expressed as $$x_i + x_j \le 1\quad (2)$$ for those pairs $(i,j)$ where $d_i + d_j \le \underline{D}.$ In other words, we exploit the fact that we know the distances at the outset to precompute which pairs of points can / cannot coexist, and just rule out the pairs that cannot. Since (1) is equivalent to $$x_i + x_j \le 1 + \frac{d_{i,j}}{\underline{D}},$$ constraint (2) is clearly at least a bit tighter than constraint (1).

Erwin started with a problem size of 50 points for demonstration purposes, then doubled that to compare timing of this two models. I ratcheted the problem size up to 1,000 points to compare his linear model to mine. (I did not test the quadratic model at that size.) As with all things MIP, the results were not entirely consistent. In limited testing, the model using (2) was usually faster than the model using (1), but occasionally (1) proved faster. The run time differences were not large enough to be exciting. For instance, in one test run version (1) needed 4.633 seconds versus 2.987 seconds for version (2).

Overall, I can't say the time differences lived up to my expectations, and the fact that at least occasionally (1) was faster than (2) (perhaps due to some quirk in presolving, or just to some random choices in branching) is consistent with my experience that MIP behaviors are, well, not consistent.

Scheduling a Round-Robin Tournament

Once in a while I come across a scheduling problem, and of course my first reaction is to think "integer program". A while back, for example, I used an IP model to work out a schedule for a rotating duplicate bridge game (in which both teams and hosts rotated) at the request of a buddy. Most recently, I saw a question on OR Stack Exchange ("Doubles Round Robin Sorting Algorithm") related to tournament scheduling. 

The problem involves six players playing pickleball (so two players on each team, with two sitting out, for each game). Given six players, there are 15 possible teams (pairings). Twelve games are scheduled each week for four weeks, with two sets of six games per week. The author of the question correctly computed that there are 45 possible game configurations. Over the course of the four weeks, he wanted every possible game played at least once (which leaves the final three game slots to be filled arbitrarily). The following conditions must be met:

• within each set of six games, every player plays four games and sits out two;
• no player sits out two consecutive games within the same set;
• no two players are partners more than once per set.

The problem poses no criterion for selecting among feasible schedules; we just want to find any one schedule that works.

My IP formulation can be found in my answer to the OR SE question. I will just mention that it uses binary variables $x_{g,s}=1$ if game $g$ goes in slot $s$ and 0 if not. Games are enumerated up front and indexed from 1 to 15. Slots refer to positions in the schedule and are numbered from 1 to 48, with six slots per set and 12 slots per week. Since no criterion is specified, we just use the default (minimize 0).

I also tried a constraint programming model, using general integer variables $s_1,\dots,s_{48},$ where $s_j \in {1,\dots,15}$ is the index of the game played in slot $j$ of the schedule. My CP formulation uses the "all different" constraint (fairly ubiquitous among CP solvers) to ensure that the first 45 slots each contain a different game. It uses the CP Optimizer "distribute" constraint to ensure that no game is played more than twice and the CP Optimizer "count" constraint to ensure that each player plays exactly four times per set (and thus sits twice) and that no team plays more than once in a set. I'm not sure how common those types of constraints are among CP solvers because I don't have much experience with CP solvers.

As it turns out, both CPLEX (for the IP model) and CP Optimizer (for the CP model) produced feasible schedules in about a second or so on my desktop PC. My intuition was that a CP model would be better suited to this type of problem, because all variables are integer and a CP solver would not be doing much if any matrix arithmetic. As it turns out, it would take a much larger test case to tell whether that intuition has any merit.

If anyone wants to play with the models, my Java code is available from my university GitLab repository. Running it would require CPLEX and CP Optimizer (and not necessarily the most recent versions of either).

A Bicriterion IP Model for a Game Strategy

A question on Mathematics Stack Exchange asks how to solve an optimization problem related to a game apparently called "speedrunner". The problem boils down to selecting integer values for variables $n_a,$ $n_c$ and $n_{b,i}$ ($i=1,\dots,n_c$) so as to minimize elapsed time $$t_{\textrm{total}} =t_{a}n_{a}+\sum_{i=1}^{n_{c}}t_{b}n_{b,i}+t_{c}n_{c},$$

where  $t_a$, $t_b$ and $t_c$ are parameters with specified values. The sole constraint specified is that winnings, defined by

$$x_{\textrm{total}} = x_{0}n_{a}\prod_{i=1}^{n_{c}}n_{b,i}$$(where $x_0$ is another parameter), must be at least $\$1$ billion. We can infer from the requirement of positive earnings that $n_a \ge 1,$ $n_c \ge 1,$ and $n_{b,i} \ge 1$ for $i=1,\dots,n_c.$ For modeling purposes, we will allow the index $i$ to exceed $n_c$ and require that $n_{b,i}=0$ for $i \gt n_c.$ An integer linear programming model would be a no-brainer were it not for two things: the product form of the expression for winnings is nonlinear; and it involves the product of a variable number of variables. 

 

The approach I chose was to express the original variables in terms of binary variables. To do that, we first need upper bounds on the original variables. We get those by guessing an upper bound $T$ on $t_{\textrm{total}}.$ (If we guess too low, we will either get a solution that exceeds that upper bound or the model will become infeasible, either of which will tip us off to try a larger guess.) Once we have that upper bound, we get an upper bound for each variable by setting the other two variables as small as possible. That leads to the following upper bounds:$$N_{a} =\left\lfloor \frac{T-t_{b}-t_{c}}{t_{a}}\right\rfloor$$

$$N_{b} =\left\lfloor \frac{T-t_{a}-t_{c}}{t_{b}}\right\rfloor$$

and 

$$N_{c} =\left\lfloor \frac{T-t_{a}}{t_{c}+t_{b}}\right\rfloor .$$ 

The denominator in the third equation arises from the fact that adding 1 to $n_c$ not only directly costs $t_c$ units of time but also adds another $n_{b,i}$ variable with minimum value 1, costing $t_b$ units of time.

 

Armed with those upper bounds, we can introduce binary variables $y_j$ $(j=1,\dots,N_a),$ $w_j$ $(j=1,\dots, N_c)$ and $z_{i,j}$ $(i=1,\dots,N_c$ and $j=0,\dots,N_b)$ along with constraints making them type 1 special ordered sets (i.e., each set contains exactly one variable with value 1) and expanding the original variables in terms of them. Specifically:

• $n_{a}=\sum_{j=1}^{N_{a}}j\cdot y_{j}$ with constraint $\sum_{j=1}^{N_{a}}y_{j}=1;$ 

• $n_{c}=\sum_{j=1}^{N_{c}}j\cdot w_{j}$ with constraint $\sum_{j=1}^{N_{c}}w_{j}=1;$ and

• $n_{b,i}=\sum_{j=0}^{N_{b}}j\cdot z_{i,j}$ for $i=1,\dots,N_{c}$

  with the following constraints for all $i\in\left\{ 1,\dots,N_{c}\right\}:$

  • $\sum_{j=0}^{N_{b}}z_{i,j}=1$ (the value of $n_{b,i}$ is uniquely defined); and
    
• $z_{i,0}+\sum_{k=i}^{N_{c}}w_{k}=1$ ($n_{b,i}=0$ if and only if $n_{c}<i$).

Armed with all that, the original objective function can be expressed as minimizing$$t_{a}n_{a}+t_{b}\sum_{i=1}^{N_{c}}n_{b,i}+t_{c}n_{c},$$where the only tweak is that we now sum over a constant number $N_c$ of terms rather than a variable number $n_c,$ relying on the fact that $n_{b,i}=0$ for $i>n_c.$

 

That brings us to the nonlinear formula for winnings. The original constraint is $ x_{\textrm{total}} \ge 10^9,$ which we can rewrite as $\log(x_{\textrm{total}}) \ge \log(10^9)$ using whatever flavor logarithm you like. Expanding the logs of $n_a$ and $n_{b,i}$ in terms of the binary variables, we get$$\log(x_{\textrm{total}}) = \log(x_{0})+\sum_{j=1}^{N_{a}}\log(j)\cdot y_{j} +\sum_{i=1}^{N_{c}}\sum_{j=1}^{N_{b}}\log(j)\cdot z_{i,j}.$$So the constraint that log winnings equal or exceed the log of $10^9$ is linear in the binary variables.

 

The solution in the Math Stack Exchange post $(n_a = 7,$ $n_c = 3$ and $n_{b,1}=n_{b,2}=n_{b,3}=18)$ turns out to be optimal given the parameter values in the question, and the IP model here will correctly achieve the minimum time (approximately 52.3 minutes) ... but it will not necessarily reproduce the best winnings within that time (approximately $\$1.02$ billion). That is because there are multiple feasible solutions that hit the correct time value, with $n_a = 7$ and with $n_c = 3$ but with the 54 cumulative $n_b$ units allocated differently (for instance, $\{19, 19, 16\}$ rather than $\{18, 18, 18\}.$ To get the best possible solution, we can use a bicriterion model with lexicographically ordered objectives, first minimizing time and then maximizing winnings (by minimizing the negative of the log of winnings).

I tested that model using the Java API to CPLEX 22.1. My code is available from my university repository.

Holt Double Exponential Smoothing

Given a time series $x_t,\, t=1,2,\dots,$ presumed to contain linear trend, Holt's double exponential smoothing method computes estimates $s_t$ of the level (mean) at time $t$ and $b_t$ of the (presumed constant) slope using the following formulas: $$s_t = \alpha x_t + (1-\alpha)(s_{t-1} + b_{t-1})$$ and $$b_t = \beta(s_t - s_{t-1}) + (1-\beta)b_{t-1}$$ where $\alpha,\beta \in (0,1)$ are smoothing weights. A recent question on OR Stack Exchange asked why the second formula is based on the level estimate and not the observed value. In other words, the proposed alternative to the trend update was $$b_t = \beta(x_t - x_{t-1}) + (1-\beta)b_{t-1}.$$

The intuition for doing it Holt's way is fairly simple. If exponential smoothing is working as intended (meaning smoothing things), then the difference in level estimates $s_t - s_{t-1}$ should be less variable than the difference in observed values $x_t - x_{t-1}.$ A formal proof probably involves induction arguments, requiring more functioning brain cells than I had available at the time, so I was a bit loose mathematically in my answer on OR SE. Just to confirm the intuition, I did some Monte Carlo simulations in R. The notebook containing the experimental setup, including code, is available here. It requires the dplyr and ggplot2 library packages.

The following plots show confidence intervals over time for the errors in the level and trend estimates using both Holt's formula and what I called the "variant" method. They are from a single experiment (100 independent time series with identical slope and intercept, smoothed both ways), but other trials with different random number seeds and changes to the variability of the noise produced similar results.

In both cases, the estimates start out a bit wobbly (and the Holt estimates may actually be a bit noisier), but over time both stabilize. There does not seem to be much difference between the two approaches in how noisy the level estimates are, at least in this run. The Holt estimates may have slightly narrower confidence intervals, but that is not clear, and the difference if any seems pretty small. The Holt trend estimates, however, are considerably less noisy than those of the variant method, supporting the intuitive argument.

With CPLEX, You're Not In Until You're In

(For a suitable soundtrack for this post, try this three minute video.)

A question popped up on the CPLEX support forum that reminded me of a slightly obscure and occasionally import aspect of the CPLEX programming APIs. What follows holds true for the Java API, and I believe it applies to the C++ and maybe C APIs. It may also hold for some of the other APIs.

The questioner, working in Java, was trying to use the "annotated Benders" approach to a MIP model. The programming issue actually is not specific to Benders decomposition, annotated or otherwise. The problem occurred in a loop where the user was defining integer variables and trying to associate them with the master problem. Here's the code:

for(int k=0; k < x.length; k++) {
     x [k] = cplex.intVar(0,cluster.getNbVeh(),"x_"ez_plusk);
     cplex.setAnnotation(benders, x[k],
                          IloCplex.CPX_BENDERS_MASTERVALUE);
}

 

The error message from CPLEX was "object is unknown to IloCplex", which was understandably confusing and yet, from personal experience, predictable.

Here is the problem: at the point that variable x[k] is fed to the setAnnotation() function, x[k] is initialized (in the programming sense that it has content) but is not yet part of the model instance (since it has not be used in a constraint or objective function). In fact, even if it had been added to a constraint or objective expression, it would still not be part of the model until the constraint or objective was itself added to the model. This is despite the fact that the model instance (here cplex) was used to create the variable.

One possible fix would be to use x[k] in something that was added to the model before trying to set its annotation. A simpler fix is just to insert the line cplex.add(x[k]); in between where x[k] is defined and where the annotation is set. This nominally adds x[k] to the model (even though not in any specific role), which is enough to make it a "known object" to CPLEX.

I learned (the hard way) about this long before CPLEX added support for Benders decomposition. When you look up solution values after solving a model, CPLEX provides convenient functions to look up either the value of a single variable or the value of an array of variables. In many applications, it is tempting to use the latter. At the same time, in some applications you may want to define an array of variables but not use all of them. For instance, suppose I have a network where some nodes have demands and some do not, and I want to define a binary variable x[k] just at nodes k that do have demand. If I define x to have dimension equal to the number of nodes and then only initialize x[k] at the nodes with demands, passing x to a method to retrieves values will bomb because some of the entries of x are null. So I cleverly initialize x[k] for all k ... and the attempt to retrieve values still bombs, because x[k] was never included in the model (in any constraint or objective function) when node k has no demand. Again, the solution is to call add(x[k]) on the model object before solving, which means the model knows about x[k] even if it never appears in any part of the actual model.

"Block Party" Puzzle

A question posed on the OR Discord channel by a doctoral student led me to discover the existence of the Jane Street puzzle page. The student was asking about building a MILP model for the June 2022 puzzle, called "Block Party 4". The puzzle involves inserting numbers into a grid, with some cells already filled in. It bears a superficial resemblance to sudoku, but with a few key differences. Where a sudoku is divided into nine square regions of nine cells each, the block party puzzle grid is divided into connected regions of varying sizes and shapes. Within a region of $k$ cells, the numbers 1 through $k$ must be filled in. Finally, rather than requiring that rows and columns contain no repeated numbers, the rules require that, for each possible value $K$, if $K$ is inserted into a cell then the nearest instance of $K$ must be at distance exactly $K$ in the $L_1$ norm. So to use a 1, there must be a 1 in an adjacent cell. To use a 2, there must be a 2 in a cell two moves away but no 2 in any adjacent cell.

Since this is a problem with logic constraints and integer decisions, my instinct was to think that constraint programming would be faster than integer programming. To test this, I coded both an IP model and a CP model in Java, using CPLEX and CP Optimizer as the respective solvers. I assumed that the grid would be square, since both the June puzzle (10 x 10) and a smaller example provided (5 x 5) were. Both models can easily be adjusted for non-square grids.

Assume an $N\times N$ grid partitioned into regions, and let $M$ be the size of the largest region (and thus the largest value that can be used in the puzzle). Number the cells 1 through $N^2$ in any order. (I used a left-to-right raster scan.) For the IP model, I use binary variables $x_{i,j}$ $(i=1,\dots,N^2$, $j=1,\dots,M)$ to indicate whether value $j$ is inserted into cell $i$. For cells with known values, I fix $x_{i,j}$ to either 0 or 1 as appropriate while building the model. Also, if cell $i$ lies in a region of size $K$, then I can fix $x_{i,j}=0$ for $j>K.$

Since we just want a feasible solution, I let the IP objective function default to minimizing zero. The most obvious constraint is $$\sum_{j=1}^M x_{i,j} = 1 \quad \forall i,$$which forces a single value to be selected for each cell. Similarly, if $B$ is a block with size $K,$ then $$\sum_{i\in B}x_{i,j}=1 \quad \forall j=1,\dots,K$$forces every value from 1 to $K$ to be used exactly once in the block. Finally, for each block $B,$ each cell $i\in B$ and each legal value $j\in \lbrace 1, \dots, \vert B\vert\rbrace$ for that cell, we add these constraints: $$x_{i,j} \le \sum_{k\in N_j(i)} x_{k,j} $$ and $$x_{i,j} + x_{k,j} \le 1\quad \forall k\in N^-_j(i),$$ where $N_j(i)$ is the set of all cells at distance exactly $j$ from cell $i$ and $N^-_j(i)$ is the set of all cells at distance less than $j$ from cell $i$ (excluding cell $i$ itself). These enforce the rule that, for value $j$ to be used in cell $i,$, it must also be used in at least one cell at distance $j$ from $i$ and in no closer cell.

The CP model is a bit more straightforward to articulate. Again, there is no objective function, since we are just solving for a feasible solution. For each cell $i$, there is a single integer variable $x_i$ with domain $1,\dots,\vert B \vert$ where $B$ is the block containing cell $i.$ If we know that cell $i$ is fixed to value $k,$ we just declare $x_i$ to have domain $\lbrace k \rbrace.$ For each block, we use an "all different" constraint to enforce the requirement that the cells in the block take distinct values. For each cell $i$ and legal value $j$ for it, the implication constraint $$(x_i = j) \implies \bigvee_{k\in N_j(i)} (x_k = j)$$ where $\bigvee$ denotes disjunction ("or"), forces at least one cell at distance $j$ from $i$ to take value $j$ if cell $i$ does, while the constraints $$(x_i = j) \implies (x_k \neq j) \quad \forall k\in N^-_j(i)$$ prohibit any closer cell from using that value. (These constraints could be condensed into a conjunction on the right hand side. For reasons I have since forgotten, I did not bother to do so.)

Both models solved the 10x10 puzzle easily. My expectation was that the CP model would be faster, for several reasons. First, it has 100 general integer variables, whereas the IP model started out with 1,100 binary variables (which the presolver whittled down to 119 binary variables, compared to 90 variables for the CP model after presolving). Second, the "all different" CP constraint seems to be a more efficient way than a steaming pile of inequality constraints to enforce the rule that no two cells in the same block take the same value. Third, CP Optimizer would be doing integer arithmetic while CPLEX would be doing double precision arithmetic, and on a per-operation basis integer arithmetic should be faster. Lastly, my experience in the past has been that the one edge IP models tend to have over CP models is tighter bounds, but that has no effect in a feasibility problem (when you are not optimizing anything).

As it turns out, I was in for a surprise. Actually, make that two surprises. First, the IP model after presolving had 211 constraints, whereas the CP model after presolving had 7,399 constraints. Note that, in the implication constraints, the left side and each equality on the right side count as a constraint. I'm not sure how comparable constraints are between the two models, but I was not expecting the CP model to have so many more. Second, while both model solved in negligible time, the IP model was faster. CPLEX solved the IP model at the root node (no branching) in about 0.01 seconds on my fairly average desktop PC. CP Optimizer needed 2,678 branches and about 0.12 seconds to solve the CP model, of which 0.05 seconds was spent in the "engine" (i.e., solving) and the rest was spent in "extraction" (turning the model into something suitable for the engine).

My Java code (which requires both CPLEX and CP Optimizer but nothing else) can be found in my GitLab repository.

Left Matrix Inverses in R

The following question popped up on OR Stack Exchange: given an $m\times n$ matrix $A$ with $m > n,$ how can one find all left inverses of $A$ in R? The author mentions that dimensions in their case would be around 200x10.

A left inverse is a matrix $B\in \mathbb{R}^{n\times m}$ such that $B A = I.$ In order for a left inverse to exist, $A$ must have full column rank. If it does not, $Ax = 0$ for some nonzero $x\in \mathbb{R}^n,$ in which case $$x = Ix = (BA)x = B(Ax) = B\cdot 0 = 0,$$ a contradiction.

Henceforth we assume that $A$ has full column rank, in which case the left null space $\mathcal{N} \subseteq \mathbb{R}^m$ will have dimension $m-n.$ Now suppose that $C\in \mathbb{R}^{n\times m}$ has the property that every row of $C$ belongs to $\mathcal{N}.$ Then $CA = 0$ and so $(B+C)A = BA+0 = I,$ making $B+C$ another left inverse of $A.$ That means $A$ has an uncountably infinite number of left inverses. Conversely, if $DA=I$ then the rows of $D-B$ belong to $\mathcal{N}.$ So the set of left inverses of $A$ can be fully characterized by any individual left inverse and a basis for the left null space of $A.$

Getting this information in R is remarkably easy. There are multiple ways to compute a left inverse, but if you have the pracma library loaded, then the function pracma::pinv() can be used to compute the Moore-Penrose pseudoinverse, which is a left inverse of $A.$ To get a basis for the left null space of $A,$ we apply the function pracma::nullspace() to $A^T,$ which computes a basis for the right null space of the transpose of $A,$ and then transpose the results.

I have a small R notebook that demonstrates this on a random 200x10 matrix.

Models for a Social Network Problem

An interesting question recently popped up on Operations Research Stack Exchange. The setting is a graph $G=(V,E)$ in which path length is defined to be the number of edges on the path (i.e., all edges have weight 1). The problem is to select a subset $S\subset V$ of vertices with a specified cardinality $k$ so as to minimize the sum over all nodes of the distance from each node to the closest selected node. I will assume the graph is connected, since otherwise the objective might be undefined.

The author of the original question indicated in a comment that the context for the problem is something involving social networks, and in another comment indicated that the diameters of the graphs are relatively constant regardless of graph size. The diameter of $G$, which I will denote by $\delta(G),$ is the maximum distance between any pair of vertices in $V.$ I will denote by $D$ the set $\left\{ 0,1,\dots,\delta(G)\right\} .$

The author posed the following integer programming model, in which $x_{v,d}\in\left\{ 0,1\right\} $ is 1 if vertex $v$ has distance $d$ to the nearest selected vertex and 0 otherwise. Note that $x_{v,0}=1$ if and only if $v\in S.$ \begin{align*} \min_{x} & \sum_{v\in V}\sum_{d\in D}d\cdot x_{v,d}\\ \text{s.t.} & \sum_{v\in V}x_{v,0}=k & (1)\\ & \sum_{d\in D}x_{v,d}=1\quad\forall v\in V & (2)\\ & x_{v,d}\le\sum_{u\in N_{d}(v)}x_{u,0}\quad\forall v\in V,\forall d\in D\backslash\left\{ 0\right\} & (3) \end{align*}where $N_{d}(v)\subset V$ is the set of all nodes at (shortest) distance $d$ from $v.$ Constraint (1) ensures that $S$ has the correct cardinality, constraint (2) ensures that the distance of any node from $S$ is uniquely defined, and constraint (3) ensures that a node is at distance $d$ from $S$ only if at least one node at distance $d$ belongs to $S.$ I will refer to this as the "distance model".

The author was asking about a possible incremental approach, but I got curious about alternative models. Frequent forum contributor Rob Pratt suggested changing constraint (3) to $$x_{v,d}\le\sum_{u\in N_{1}(v)}x_{u,d-1}\quad\forall v\in V,\forall d\in D\backslash\left\{ 0\right\} \quad(3'),$$

which says that for a node $v$ to be at distance $d,$ one of its neighbors must be at distance $d-1.$ I will call that "distance model 2". Meanwhile, I thought it might help to leave $x_{v,0}$ binary but make $x_{v,d}\in\left[0,1\right]$ continuous for $d>0$ (which might or might not be equivalent to using branching priorities

to ensure that the $x_{v,0}$ variables were branched on before any

of the other variables). I will call that "distance model 3".

 

Someone else suggested what I will call the "assignment model", which uses one set of binary variables $x_{v}$ to determine which vertices are selected to be in $S$ and a second set if binary variables $y_{v,u}$ to indicate whether vertex $u$ is the closest vertex in $S$ to vertex $v.$ That model is as follows:\begin{align*} \min_{x,y} & \sum_{u,v\in V}d_{v,u}y_{v,u}\\ \text{s.t.} & \sum_{v\in V}x_{v}=k & (4)\\ & \sum_{u\in V}y_{v,u}=1\quad\forall v\in V & (5)\\ & y_{v,u}\le x_{u}\quad\forall v,u\in V & (6) \end{align*}where (4) enforces the size requirement for $S$, (5) stipulates that every vertex is assigned to a single selected vertex (possibly itself) and (6) makes sure that the assigned selected vertex is actually selected.

Lastly, I came up with yet another model, which I will call the "flow model" since it is based on treating selected vertices as sinks and vertices outside $S$ as sources in a flow model. It uses binary variables $x_{v}$ to indicate whether a vertex is selected and continuous variables $y_{u,v}\in\left[0,\vert V\vert-k\right]$ for flow volumes. Since the edges are bidirectional, for each edge $(u,v)\in E$ there will be two flow variables, $y_{u,v}$ and $y_{v,u}$ (only one of which will be nonzero in the optimal solution). The idea is that each vertex that is not selected passes along any flow arriving at it plus one unit of new flow. Selected vertices soak up whatever flow comes in. We minimize the sum of the aggregate flows across all edges, which effectively charges each unit of flow 1 for each edge it crosses. The optimal solution will therefore send each unit of flow to the selected vertex (sink) closest to its source, making the cost of each unit of flow equal to the distance from source to nearest selected vertex. That model is as follows.\begin{align*} \min_{x,y} & \sum_{(u,v)\in E}\left(y_{u,v}+y_{v,u}\right)\\ \text{s.t.} & \sum_{v\in V}x_{v}=k & (7)\\ & \sum_{u\in N_{1}(v)}\left(y_{v,u}-y_{u,v}\right)\ge1-\left(\vert V\vert-k\right)\cdot x_{v}\quad\forall v\in V & (8). \end{align*}The by now familiar constraint (7) sets the size of the selected set. Constraint (8) says that the flow out of any vertex $v$ must be one greater than the flow in \emph{unless} the vertex is selected (in which case nothing needs to flow out of it).

To assess how the various models perform, I coded them in Java using CPLEX 22.1 as the solver and ran a few experiments on randomly generated graphs. I did not do nearly enough experiments for any definitive conclusions, but I will quote the results of one that I think is somewhat informative. The test graph has $\vert V\vert=2,000,$ $\vert E\vert=23,360$ and diameter $\delta(G)=5.$ Each model was run for 10 minutes (not including the time spent constructing the model). The next table summarizes the results.

	Distance	Distance2	Distance3	Assignment	Flow
Binary variables	9,976	12,000	2,000	4,002,000?	2,000
Total columns	9,976	12,000	9,976	4,002,000?	48,720
Total rows	9,977	12,001	9,977	2,001?	2,001
Nonzero coefficients	4,017,952	257,600	4,017,952	12,002,000?	97,440
Objective value	3,202	3,192	3,181	none	3,506
Lower bound	3,139.7	3,139.2	3,143.3	none	1,980

 

None of the models reach proven optimality, and in fact the assignment model hit the time limit early in the presolve phase, before CPLEX printed any statistics about dimensions. All the output I got was that presolve "has eliminated 0 rows and 0 columns..." The dimensions I listed are the dimensions for the paper model, before any presolve reductions.

 

If you are wondering about why the "Distance2" model (which is the original distance model with Rob's modification to constraint (3)) has larger row and column dimensions than the original, it turns out the both start with the same initial dimensions but the CPLEX presolver removes a bunch of rows and columns in the original model that it cannot remove from Rob's version. Still, Rob's version winds up with an order of magnitude fewer nonzero coefficients than the original version (or my tweak to it, "Distance3").

 

Based on this and a few other preliminary runs, there are a handful of takeaways that I am somewhat comfortable in saying.

• As graph size grows, the assignment model fairly quickly becomes too large to use. Hypothetically it could reach proven optimum faster than the others given a liberal time limit, but the betting line is against that.
• Of the remaining models, my flow model has the most columns but the fewest rows and the fewest nonzeros. Unfortunately, it also has the worst performance. On a couple of other tests it did better, at least early on, with the incumbent solution value, but it seems to have the weakest bounds. In the interest of salvaging a little bit of my bruised pride, I will note that fewest nonzeros means that, as the graph grows, it might at some point be the only one of these models to fit in memory.
• The tweak I made to the original model ("Distance3") did best in both incumbent value and bound ... on this example ... within the 10 minute run time limit. There is no guarantee this holds up in other cases, and it ties with the original model for largest constraint matrix (excluding the assignment model).
• Rob's tweak has more rows and columns than the original model (or my tweak), but not hugely more, and it has the fewest nonzeros among the distance models. So it is definitely a contender for the production model, at least pending more testing.

Source code (in Java) that generates a random graph and tests the model is available from my repository.

Partitioning an Interval

I recently saw a question on a help forum that fits the following pattern. The context is an optimization model (mixed integer program). There is a continuous variable $x$ and a constant value $a$ (frequently but not always 0), and we want to distinguish among three cases (with different consequences in the model): $x<a;$ $x=a;$ or $x>a.$ Each case has separate consequences within the model, which I will call $C_1,$ $C_2$ and $C_3$ respectively. Variations on this question arise frequently. For instance, make $x$ the difference of two variables, set $a=0$ and you are distinguishing whether the difference is negative, zero or positive.

To make things work properly, we need $x$ to be bounded, say $L\le x \le U.$ The goal is to break the feasible range of $x$ into three intervals. To do so, we will introduce a trio of binary variables, $y_1, y_2, y_3$ together with the constraint $$y_1 + y_2 + y_3 = 1.$$ We will come up with constraints such that fixing $y_1 = 1$ puts you in the left portion of the domain, fixing $y_2 = 1$ puts you in the middle portion, and fixing $y_3 = 1$ puts you in the right portion. The $y$ variables are then used elsewhere in the model to enforce whichever condition $C$ applies.

I'm using three variables for clarity. You can get by with two binary variables (changing the equality constraint above to $\le$), where both variables equaling zero defines one of the domain intervals. Figure 1 shows what the user wants and how the $y$ variables relate to it.

Figure 1

The intervals for $x$ are $[L, a)$ when $y_1 = 1$, the singleton $[a, a]$ when $y_2 = 1,$ and $(a, U]$ when $y_3 = 1.$ Unfortunately, the user cannot have what the user wants because the feasible region of a MIP model must be closed, and the first and third intervals in Figure 1 are not closed. Closing them results in Figure 2.

Figure 2

The intervals for $x$ are now $[L, a],$ $[a, a]$ and $[a, U].$ The good news is that this decomposition is easy to accomplish. The bad news is that the user likely will not accept it. If $x=a$, any one of the $y$ variables could take the value 1, so any of the three conditions could be triggered.

This brings us to the first (and more common) of two possible compromises. We can change the strict inequality $x > a$ to the weak inequality $x \ge a + \epsilon$ where $\epsilon$ is some small positive number, and do something analogous with the left interval. The result is Figure 3.

Figure 3

Now $y_1=1 \implies x \le a-\epsilon,$ $y_2 = 1 \implies x=a,$ and $y_3=1 \implies x \ge a + \epsilon.$ The good news is that all three intervals are closed. The bad news is that values of $x$ between $a-\epsilon$ and $a$ or between $a$ and $a + \epsilon$ are suddenly infeasible, whereas they were feasible in the original problem. Also note that any tiny deviation from $a$ will throw $x$ into no man's land. That leads to one more possibility, involving yet another positive constant $\delta < \epsilon$ and shown in Figure 4.

Figure 4

In this version, the domain of $x$ is broken into the closed intervals $[L, a-\epsilon],$ $[a-\epsilon +\delta, a+\epsilon - \delta]$ and $[a+\epsilon, U].$ There are still values of $x$ that were feasible in the original model but no longer feasible, but now you get to count values of $x$ "close" to $a$ as signalling the second of your three conditions.

The algebra to put either Figure 3 or Figure 4 into force is actually pretty straightforward. You just need to write a pair of inequalities $\dots \le x \le \dots$ where the left side expression is the sum of each $y$ variable times the lower bound that would apply when that variable is 1 and the right expression is the sum of each $y$ variable times the upper bound that would apply. So for Figure 3, where the intervals are $[L, a-\epsilon],$ $[a,a]$ and $[a+\epsilon, U]$, we would have $$Ly_1 + a y_2 + (a+\epsilon)y_3 \le x \le (a-\epsilon)y_1 + a y_2 + Uy_3.$$ For Figure 4, the constraints would be $$Ly_1 + (a-\epsilon+\delta)y_2 + (a+\epsilon)y_3 \le x \le (a-\epsilon)y_1 + (a+\epsilon-\delta) y_2 + Uy_3.$$

There is one "tactical" point to consider. When this is first explained to someone who was unaware that strict inequalities are verboten, they are often tempted to set $\epsilon = 10^{-G}$ where $G$ is the gross domestic product of their native country. The problem is that the solver is using finite precision computer arithmetic, and every solver has a tolerance value $\tau$ (small but not zero) such that coming within $\tau$ of satisfying a constraint is "close enough". If you pick $\epsilon$ (or $\delta$) too small, it has the same consequence as setting it equal to 0 in terms of how valid the solutions are. You can end up with a value of $a$ for $x$ (to within rounding error) triggering consequence $C_1$ or $C_3$ rather than $C_2$, or a value of $x$ strictly greater than $a$ triggering $C_2$ (or possibly even $C_1$), and so on. So $\epsilon$ (and, if needed, $\delta$) must be greater than the rounding tolerance used by the solver.

Allocating Resource Sets

The following problem was posted on Operations Research Stack Exchange. A system contains $K$ users and $N$ resources. Each unit of resource may be allocated to at most one user. Each user $k$ requires a specified number $d_k$ of resource units, which must be consecutive. Not all resource sequences of the proper length will be acceptable to a user. Citing an example from the original post, you might have $d_1=3,$ with user 1 accepting only one of following sets: $\{1, 2, 3\},$ $\{7, 8, 9\},$ $\{11, 12, 13\},$ or $\{17, 18, 19\}.$ The objective is to assign resources to as many users as is possible.

Formulating this as an integer linear program is straightforward, and I coded the IP model in Java (using CPLEX as the solver) to provide a benchmark. The author of the question, however, was looking for heuristic solutions. I suggested a few possibilities, and decided to code two of them just to see how well they did. The setup for all of them is identical. You start with the following elements:

• the set of unsatisfied users (initially, all users);
• an enumeration of all resource sets compatible with any user (with each such set represented by an integer ID number);
• a mapping of each user ID to the set of IDs of all compatible resource sets;
• a mapping of each resource set ID to the set of IDs of all users who would accept that set; and
• a mapping of each resources set ID to the set of IDs of all other resources sets that conflict with that set.

Two resource sets conflict if they intersect, in which case allocating one of them precludes allocating the other since each unit of resource can be used at most once.

All the heuristics I suggested work by finding a valid allocation (an unused resource set that does not conflict with any resource set already used and an user who has not yet been served and will accept that resource set), making that allocation, and then updating the mappings described above. Updating the mappings means removing the user who just received resources, removing the resource set just assigned, and removing any other unassigned resource sets that conflict with the set just assigned. Those changes can have "ripple effects": removing a user may result in a surviving resource set having no compatible users left (in which case the resource set can be removed), and removing a resource set (whether used or due to a conflict) may leave a user with no surviving resource sets that are compatible, in which case the user can be removed. So the update step involves some looping that must be coded carefully.

The various heuristics I suggested are distinguished by two fundamental choices. First, in each iteration do you pick an available resource set and then look for a user who will accept it, or do you pick a user who has not yet been served and then look for a compatible resource set that is still available? Second, regardless of order, what criteria do you use for selecting users and resource sets?

There are a lot of ways to make those choices, and I home in on two. My first approach starts by selecting the available resource set with the fewest remaining conflicts and then chooses the compatible user having the fewest surviving options for resource sets. My second approach starts by selecting the remaining user with the fewest surviving options for resource sets and then choosing the compatible resource set with the fewest remaining conflicts. In all cases, ties are broken randomly. My logic is that picking the resource set with the fewest conflicts will leave the most surviving resource sets and (hopefully) allow more users to be served, and picking the user with the fewest remaining options will (hopefully) reduce the number of users who are frozen out because all compatible resource choices have already been allocated.

I'll take a moment to note here that the two approaches I just stated are intended to be one-pass heuristics (find a feasible allocation and stop). You could rerun them with different random seeds, but that would only change the results (not necessarily for the better) if one or more ties had occurred during the first pass. Another possibility, which I did not bother to code, would be to select either resource set or user randomly at each stage, then select the other half of the assignment randomly from the compatible choices. I suspect that any single run of the random approach would likely do worse than what I described above, but you could keep rerunning the purely random heuristic for a specific number of iterations (or with a time limit) and track the best solution ever found. That might improve over the versions I tested.

Using the dimensions specified (in a comment, replying to me) by author of the question, I did a small number of tests. In those tests, the resource set first heuristic consistently beat the user first heuristic, and both exhibited what I would consider to be decent results. On three test runs with different seeds for the random problem generator, I got results of 14/13/11, 15/14/11 and 14/13/10, where the first number is the optimal number of customers served (from the IP model), the second is the number served by the resource-first heuristic, and the third is the number served by the customer-first heuristic. Run times for the heuristics on my humble PC (including setup times) were minuscule (under 20 milliseconds).

My Java code can be found here.

Wolf, Goat and Cabbage Part II

This continues my previous post about the "Wolf, Goat and Cabbage" logic puzzle. Using a MIP model to solve it strikes me as somewhat analogous to hammering in a nail with the butt end of a screwdriver handle: it works, but maybe it's not the ideal tool. To me, a constraint solver would make more sense, so I coded up a model using IBM's CP Optimizer (henceforth "CPO", part of the CPLEX Optimization Suite). Unsurprisingly, it worked (after some debugging) and produced the same solution.

MIP solvers largely share the same "vocabulary" for building models (real / integer / binary variables, linear and maybe quadratic expressions, equality and inequality constraints). From my limited exposure to constraint solvers, there is significant variation in both what things the solver does and does not understand. Some of that is variable types. A very basic solver may understand logical (true/false) and integer variables, and maybe real-valued variables (although I'm not sure handling real variables is anywhere near universal). CPO (and presumably some other solvers) understand "interval variables", which as the name suggests represent intervals of discrete values (usually time intervals, though possibly location or some other aspect). Similarly, different solvers will understand different types of global constraints. I suspect that every CP solver worth mentioning understands "all different" (no two variables in a bunch of integer variables can take the same value), but some solvers will implement "no overlap" constraints (the time interval during which I am eating and the time interval during which I am showering cannot overlap) or precedence constraints (this job has to end before this other job can start). Those kinds of constraints make certain scheduling problems easier to solve with CP than with a MIP model.

Anyway, I'm not entirely new to CPO, though far from proficient, and I tripped over a few "features" while coding the puzzle. I wanted to use boolean (true/false) variables for certain things, such as whether an item had made it to the far side of the river (true) or was stuck on the near side (false). CPO lets you declare a boolean variable but then treats it as an integer variable, meaning that you need to think in terms of 0 and 1 rather than false and true. So you can't say "if $x$ then ..."; instead, you need to say "if $x = 1$ then ..." (and trust me, the syntax is clunkier than what I'm typing here). When you go to get the value of your boolean variable $x$ after solving the model, CPO returns a double precision value. CPLEX users will be used to this, because in a MIP model even integer variables are treated as double-precision during matrix computations. CP solvers, though, like to do integer arithmetic (as far as I know), so it's a bit unclear why my boolean variable has to be converted from double precision to integer (or boolean). Even odder is that, at least in the Java API, there is a method that returns the value of an integer variable as an integer if you pass the name of the variable as the argument, but if you pass the actual variable you are going to get a double. (Did a federal government panel design this?)

In any event, logic of the CPO model is moderately straightforward, with constraints like "you can't carry something in the boat if it isn't on the bank the boat departs from" and "if the wolf and goat end up in the same place at the end of a period, the farmer better end up there too". Some things are bit less clunky with CPO than with CPLEX. For instance, to figure out what (if anything) is in the boat at a given time, the MIP model requires binary variables subscripted by time and item index (1 if that item is in the boat on that trip 0 if not). The CPO model just needs an integer variable for each time period whose value is either the index of the thing in the boat or a dummy value if the boat is empty. Furthermore, the nature of the variable automatically takes care of a capacity constraint. Since there is only one variable for what's in the boat, at most one thing (whatever that variable indicates) can be in the boat.

Some (most?) constraint solvers, including CPO, provide a way to use a variable as an index to another variable. In my code, the integer variable indicating what's in the boat at time $t$ is used to look up the location variable (near or far bank) for that item at time $t$ from a vector of location variables for all items at time $t$.

Anyway, the code in my repository has been updated to include the CPO model, and it's heavily commented in case you wanted to compare it to the MIP model.

Wolf, Goat and Cabbage

On Operations Research Stack Exchange, someone asked about a possible connection between the "wolf, goat and cabbage" logic puzzle and Monge's optimal transport problem. In the logic puzzle, a farmer has to get a wolf, a goat and a cabbage across a river using a boat that can only accommodate one of them (plus the farmer) at a time. If you leave the wolf and goat alone together at any point, the wolf eats the goat. If you leave the goat and cabbage alone together at any point, the goat eats the cabbage. Fortunately, the wolf has no appetite for cabbage and the cabbage does not seem to want to eat anything, else the problem would be infeasible.

Neither Monge's transport problem nor the more commonly taught (in my opinion) Hitchcock transportation problem directly apply, although you can (almost) treat the puzzle as a multiperiod commodity flow with an "inventory" of each item (wolf, goat, cabbage) on each side of the river. The "almost" part is that you need some of the variables to be integer, for two reasons. One is that the LP relaxation of the logic constraints (e.g., inventory of wolf + inventory of goat $\le 1$ on this side of the river at this time) will result in fractional values (we'll leave half a wolf and half a goat here and carry the other halves across the river) (which would greatly diminish the values of both wolf and goat). The other is that the objective is to minimize the number of trips made. It would be tempting to just assign a cost of 1 to each movement of an object in either direction, but the catch is that you will occasionally cross with nothing in the boat (besides the farmer). Those "deadheading" trips count toward the objective, but it's tricky to assign a cost to a zero flow.

To fill in some idle time, I coded up a MIP model. Mind you, I am not advocating MIP as a way to solve problems like this; I just wanted to confirm my thinking (in particular, that an LP commodity flow model would have fractional solutions). Assume that the farmer arrives at the left bank at time 0 with all three items, and that each trip (in either direction) counts as one time unit, with the first trip occurring at time 1. We need to set an upper bound $T$ on the number of trips. Since the state of the system is described by the location of four things (counting the farmer), with each have two possible locations (left bank, right bank), $T=2^4 =16$ works. The set of items will be denoted $I=\lbrace W, G, C\rbrace.$ My formulation uses the following variables.

• $L_{i,t}\in [0,1]$ and $R_{i,t}\in [0,1]$ are the inventories of item $i\in I$ at time $t\in \lbrace 0,\dots,T$ on the left and right banks respectively, after any trip occurring in that period.
• $x_{i,t}\in \lbrace 0,1 \rbrace$ and $y_{i,t}\in \lbrace 0,1 \rbrace$ are the amount of item $i$ crossing the river at time $t$ from left to right or right to left respectively.
• $z_t\in \lbrace 0,1 \rbrace$ is 1 if transport is ongoing and 0 if we are done (the farmer and all three items are on the right bank).

It would be perfectly fine (but unnecessary) to make the inventory variables integer-valued, and we could also make the inventory variables integer-valued and drop the integrality restrictions on the cartage variables ($x$ and $y$).

Some of the variables can be fixed at the outset.

• We start with all inventory on the left bank, so $L_{i,0}=1$ and $R_{i,0}=0$ for all $i\in I.$ 
• There is no trip at time 0, so $z_0=0$ and $x_{i,0}=y_{i,0}$ for all $i\in I$.
• Trips alternate left-to-right (odd time periods) and right-to-left (even time periods), so $x_{i,t}=0$ for all $i\in I$ and for all even $t$ and $y_{i,t}=0$ for all $i\in I$ and for all odd $t$.
  

The objective function is to minimize the number of trips required. $$\min \sum_{t=1}^T z_t.$$

The constraints are rather straightforward.

• The inventory on either bank in any period is the inventory on that bank from the preceding period, plus any arriving inventory and minus any departing inventory. So for $t\ge 1$ $$L_{i,t} = L_{i, t-1} - x_{i,t} + y_{i,t}\quad \forall i\in I$$ and $$R_{i,t} = R_{i,t-1} + x_{i,t} - y_{i,t}\quad \forall i\in I.$$
• In an odd numbered period (where the farmer ends up on the right bank), neither wolf and goat nor goat and cabbage can be on the left bank. So for odd $t$ $$L_{W,t} + L_{G,t} \le 1$$ and $$L_{G,t} + L_{C,t}\le 1.$$
• In an even numbered period (where the farmer ends up on the left bank), neither wolf and goat nor goat and cabbage can be on the right bank unless the problem is completed ($z_t = 0$), in which case the farmer remains on the right bank. So for even $t$ $$R_{W,t}+R_{G_t} + z_t \le 2$$ and $$R_{G,t} + R_{C,t} + z_t \le 2.$$
• Transport continues until the left bank is empty. $$3z_t \ge \sum_{i\in I} L_{i,t - 1}\quad \forall t\ge 1.$$

It does indeed produce a correct solution, using seven trips (see the Wikipedia page for the solution) ... and with integrality conditions dropped it does indeed produce a nonsense solution with fractions of items being transported.

Java code for this model (using CPLEX) is in my Git repository.

Finding Almost All Paths

A question posted on Stack Overflow (and subsequently deleted) led to a blog post by Erwin Kalvelagen on how to find all paths between two nodes in a directed graph (possibly with self-loops, i.e. arcs from a node to itself) subject to two constraints: no arc can be used more than once in a path; and there is an upper limit $M$ on the number of arcs used. Note that a path might visit a *node* more than once. It just cannot repeat an arc. The original question seems to have referred to an undirected graph, but Erwin's post works with directed graphs and so will I.

Erwin explored some mixed integer linear programming (MIP) models in his post, and a subsequent post on OR Stack Exchange led to more proposals of MIP models (including one from me). I also suggested that a "brute force" approach might be faster than any of the MIP models. In what follows, I will spell out both my MIP model and the brute force approach I used. Java code for both (which requires CPLEX and the Apache Commons Collections library) are in my code repository.

In what follows $A$ is the set of arcs in the graph, $s$ is the origin node for all paths, $t$ is the destination node for all paths, and $M$ is the maximum number of arcs to include in a path.

MIP model

 

The MIP model uses the following variables. 

• $u_{a}\in\left\{ 0,1\right\} $ is 1 if and only if arc $a$ is used on the path.
• $f_{a}\in\left\{ 0,1\right\} $ is 1 if and only if arc $a$ is the first arc on the path.
• $\ell_{a}\in\left\{ 0,1\right\} $ is 1 if and only if arc $a$ is the last arc on the path.
• $y_{ab}\in\left\{ 0,1\right\} $ is 1 if and only if arc $b$ immediately follows arc $a$ on the path.
• $z_{a}\in\left[0,M\right]$ will be the number of arcs preceding arc $a$ on the path (0 if $a$ is not on the path).

Some of the variables can be eliminated (fixed at 0) at the outset.

• $f_{a}=0$ if node $s$ is not the tail of arc $a.$
• $\ell_{a}=0$ if node $t$ is not the head of arc $a.$
• $y_{ab}=0$ if the head of arc $a$ is not the tail of arc $b.$

Since we are just interested in finding feasible solutions, the objective is to minimize 0.

Use of the $z$ variables mimics the Miller-Tucker-Zemlin approach to avoiding subtours in the traveling salesman problem. A common knock on the MTZ formulation for the TSP is that it has a somewhat loose continuous relaxation. Since we have a trivial objective (all feasible solutions are optimal), that is not a concern here.

The constraints are as follows.

• There must be one first arc and one last arc.
  $$\sum_{a\in A}f_{a}=1.$$$$\sum_{a\in A}\ell_{a}=1.$$
• At most $M$ arcs can be used.$$\sum_{a\in A}u_{a}\le M.$$
• An arc is used if and only if it is either the first arc or follows another arc on the path.$$f_{a}+\sum_{b\in A}y_{ba}=u_{a}\quad\forall a\in A.$$
• The last arc must be a used arc.$$\ell_{a}\le u_{a}\quad\forall a\in A. (1)$$
• The sequence value of an unused arc is 0.$$z_{a}\le Mu_{a}\quad\forall a\in A.$$
• No arc can follow the last arc.$$\ell_{a}+\sum_{b\in A}y_{ab}\le1\quad\forall a\in A. (2)$$
• If an arc is used, either it is the last arc or another arc follows it.$$\ell_{a}+\sum_{b\in A}y_{ab}=u_{a}\quad\forall a\in A. (3)$$
• If an arc $b$ follows arc $a$, the sequence number of arc $b$ must be one higher than the sequence number of arc $a.$ $$z_{a}-z_{b}+\left(M+1\right)y_{ab}\le M\quad\forall a,b\in A,a\neq b.$$

Over on OR Stack Exchange, Rob Pratt correctly pointed out that constraint (3) implies constraints (1) and (2). I've left them in the Java code anyway. The CPLEX presolver removes them automatically.

Finding all solutions 

To find all solutions, one possible approach is to solve whatever MIP model you choose, then add a "no-good" constraint that eliminates the solution just found (and only that one) and solve again, until eventually the aggregation of "no-good" constraints makes the model infeasible. What I did instead was to use the "populate" command in CPLEX, which accumulates a pool of solutions. Besides a time limit, I used two non-default parameter settings: I cranked up the solution pool capacity (the maximum number of solutions to find) to something high enough to let it find all solutions; and I set the solution pool intensity to its highest value (4), which tells CPLEX to aggressively seek out all feasible solutions.

Brute force approach

 

The brute force approach is remarkably straightforward. We will use a queue of (incomplete) paths that I will call the "to-do list". Start by creating a length one path for each arc with tail $s$ and add them to the to-do list. We now proceed in a loop until the to-do list is empty. At each iteration, we pull a path $P$ off the to-do list, identify the arcs whose tails match the head of the last arc in $P$, remove any arcs already on $P$, and for each surviving arc $a$ create a new path $P'$ by extending $P$ with $a$. If the head of arc $a$ is $t$, $P'$ is a new $s-t$ path, which we record. Either way, if $P'$ has length less than $M$, we add it to the to-do list, and eventually try to extend it further.

 

Do they work?

 

Would I be posting this if they didn't. :-) I tested both methods on the digraph from Erwin's post, which has 10 nodes and 22 arcs (with two self-loops). The source and sink are nodes 1 and 10 respectively. With $M=3$ there are four paths (which both methods find), and with $M=4$ there are nine paths (which both methods find). In both cases, brute force took about 1 ms. on my PC (using non-optimized Java code with a single thread). CPLEX times were rather stochastic, but I think it fair to say that building the models took around 55+ ms. and solving them typically took 20 ms. or more.

When I set a maximum length ($M$) of 10, things got interesting. The brute force approach found 268 paths (in about 6 ms), while CPLEX found only 33. Neither time limit nor pool size were a factor, so I assume that this is just a limitation of the aggressive setting for pool intensity. That means that to find all possible solutions using CPLEX, the solve / add constraint / solve again approach would be necessary.

A "Decoupled" Quadratic Program

Someone posted a question on OR Stack Exchange about a problem with a "nonseparable bilinear objective function" with "decoupled constraints". The problem has the following form:

\begin{alignat*}{1} \min & \sum_{i=1}^{m}\sum_{j=1}^{n}a_{ij}x_{i}y_{j}+b^{\prime}x+c^{\prime}y\\ \textrm{s.t. } & x\in X\subset\mathbb{R}^{m}\\ & y\in Y\subset\mathbb{R}^{n} \end{alignat*}

where $X$ and $Y$ are polytopes (i.e., defined by linear constraints, and bounded) in the positive orthants of their respective spaces (i.e., $x\ge 0$ and $y\ge 0$) and $a$, $b$ and $c$ are all nonnegative. So besides everything being nonnegative, the key things here are that the objective contains bilinear terms (always involving the product of an $x$ and a $y$) and each constraint involves either only $x$ or only $y$. The author was looking for a way to exploit the separability of the constraints in solving the problem.

It occurred to me that a heuristic approach might be to solve a sequence of linear programs, alternating between $X$ and $Y$. Let $h(x,y)$ be the objective function of the original problem, and let $$f(x;y) = \sum_i\sum_j a_{ij}x_i y_j + b^\prime x$$and $$g(y;x)=\sum_i\sum_j a_{ij}x_i y_j + c^\prime y$$ be respectively the portions of the objective dependent on $x$ with $y$ fixed or dependent on $y$ with $x$ fixed. Each is linear in one set of variables (the other set being fixed). So we could proceed as follows:

1. Minimize $f(x;0)$ over $X$ (a linear program) to get a starting value $x^0\in X.$
2. Minimize $g(y;x^0)$ over $Y$ to get a starting value $y^0\in Y.$ We now have an incumbent solution with objective value $h(x^0,y^0)=b^\prime x^0 + g(y^0;x^0).$ Set $t=0$.
3. Repeat the following until the first time that the incumbent does not improve.
1. Minimize $f(x;y^t)$ over $X$ to get $x^{t+1}.$ If $f(x^{t+1},y^t) + c^\prime y^t$ is less than the incumbent value, make $(x^{t+1}, y^t)$ the new incumbent, else punt.
2. Minimize $g(y;x^{t+1})$ over $Y$ to get $y^{t+1}.$ If $g(y^{t+1};x^{t+1}) + b^\prime x^{t+1}$ is less than the incumbent value, make $(x^{t+1},y^{t+1})$ the new incumbent and increment $t$, else punt.

This will generate a sequence of solutions, each a corner point of the feasible region $X\times Y,$ with monotonically decreasing objective values.

Before continuing, it is worth noting that we are guaranteed that at least one corner of $X\times Y$ will be an optimum. This is of course always true when the objective is linear, but not always true with a quadratic objective. In our case, suppose that $(x^*, y^*)$ is an arbitrary optimum for the original problem. Then $x^*$ must minimize $f(x;y^*)$ over $X$, so either $x^*$ is a corner of $X$ of (if there are multiple optimal) $x^*$ can be replaced by a corner of $X$ with the same value of $f(x;y^*)$ (and thus the same value of $h(x;y^*)$, since the difference $c^\prime y^*$ does not depend on $x$). Apply the same logic on the other variable to show that $y*$ is either a corner of $Y$ or can be replaced by one.

I'm still calling this a heuristic, because there is one more piece to the puzzle. Could the procedure stop at a corner of $X\times Y$ that is a local but not global optimum? I'm not sure. Offhand, I do not see a way to prove that it will not, but I also cannot easily conjure up an example where it would.

To test this (and to confirm that I was not hallucinating, which has been known to happen), I wrote some Java code to generate random test problems and try the procedure. The code uses CPLEX to solve the LPs. In all test cases, it terminated with a solution (at least locally optimal) in a pretty small number of iterations. 

As a benchmark, I tried solving the full QP models with CPLEX, setting its "optimality target" parameter to "OPTIMALGLOBAL", which tells CPLEX to search for a global optimum to a nonconvex problem. This causes CPLEX to turn the problem into a mixed-integer quadratic program, which shockingly takes longer to solve than an LP. In a limited number of test runs, I observed a surprisingly consistent behavior. At the root node, CPLEX immediately found a feasible solution and then immediately found a better solution that matched what my procedure produced. After than (and within a usually stingy time limit I set), CPLEX made progress on the bound but never improved on the incumbent. In two test runs, CPLEX actually reached proven optimality with that second incumbent, meaning my procedure had found a global optimum.

So perhaps my "heuristic" can actually be shown to be an exact algorithm ... or perhaps not. At least in my test runs, CPLEX working on the QP found the best solution about as fast as, or maybe slightly faster than, my procedure did. On the other hand, my procedure only requires an LP solver, so it will work with code that does not accept QPs.

My Java code (which requires CPLEX) is available here.

Addendum: User "Dusto" on the Discord Operations Research server posted a simple counterexample to global convergence. The example has no constraints other than bounds on the variables (from 0 to 10 in all cases). The $b$ and $c$ vectors are strictly positive, so the linear programs in my heuristic will start at the origin and get stuck there. The $A$ matrix is crafted so that a negative overall objective value is attainable.

Tournament Scheduling: CPLEX v. CP Optimizer (Part 3)

This is the third and final chapter in my opus about scheduling "pods" (players) in a tournament. Reading the first post will be essential to understanding what is going on here. Reading the second post (in which I formulate an integer programming model for the problem) is definitely optional.

I will stick with the notation introduced in the prior post. As before, there are $N$ pods (players) being organized into teams of two to play in $G$ games (two teams per game, one in white, one in black). Each game has two slots corresponding to the two teams in the game.

• $t$ indexes a team;
• $p$ and $q$ index pods;
• $g$ indexes a game;
• $s$ indexes a slot (and $s'$ is the other slot of the same game);
• $c$ is a jersey color (0 for white, 1 for black).

For a slot $s$, I will use $G_s$ and $C_s$ to denote respectively the game in which the slot exists and the jersey color (0 or 1) of the team in the slot. For a team $t$, $P_{t,0}$ and $P_{t,1}$ will be the two pods on the team. (The order they are listed is immaterial.)

The model variables are almost (but not exactly) what they were in the IP model.

• $x_{t}\in \lbrace 0, \dots, 2G-1\rbrace$ is the index of the slot in which team $t$ plays (where slots 0 and $G$ are the white and black teams in the first game and slots $G-1$ and $2G-1$ are the white and black teams in the final game).
  
• $y_{pqg}\in \lbrace 0,1\rbrace$ is 1 if pods $p$ and $q\neq p$ are playing in game $g$ on opposing teams.
  
• $z_{pg}\in \lbrace 0,1\rbrace$ is the color jersey worn by pod $p$ at the conclusion of game $g$ (regardless of whether or not $p$ played in game $g$).
• $w_{pg}\in \lbrace 0,1\rbrace$ is 1 if pod $p$ changes jersey color going into game $g.$
• $v_{pg} \in \lbrace 0,1\rbrace$ is 1 if pod $p$ is playing in game $g.$

The changes from the IP model are that $x$ is general integer rather than binary (with dimension 1 rather than 2), the third index of $y$ is the game rather than the slot, and $v$ is a new variable. As in the IP model, the objective is to minimize $\sum_p \sum_g w_{pg}.$

The constraints are as follows. Note that the requirement that every team play exactly once is captured by the assignment of a single slot value to each team (via $x$).

• Two different teams cannot occupy the same slot: $$\textrm{allDiff}(x).$$
• Occupying a slot implies playing in the game: $$x_t = s \implies (v_{P_{t,1},G_s} = 1 \wedge v_{P_{t,2},G_s} = 1) \quad \forall t,s.$$
• Occupying a slot determines the color of the jersey worn in the game: $$x_t = s \implies  (z_{P_{t,1},G_s} = C_s \wedge z_{P_{t,2},G_s} = C_s) \quad \forall t,s.$$
• Jersey color for a pod remains constant from game to game unless a change is recorded: $$ z_{p,g} \neq z_{p,g-1}  \iff w_{p,g} = 1 \quad \forall p, \forall g > 0.$$
• Playing in consecutive games precludes changing jerseys: $$(v_{p,g - 1} = 1 \wedge v_{p,g} = 1) \implies w_{p,g} = 0 \quad \forall p, \forall g > 0.$$
• Two pods are opponents if and only if they are playing in the same game with different colors: $$y_{pqg} = 1 \iff (v_{pg} = 1 \wedge v_{qg} = 1 \wedge z_{pg} \neq z_{qg} \quad \forall p, \forall q\neq p, \forall g.$$
• Every pair of pods faces each other exactly twice: $$\sum_g y_{pqg} = 2 \quad \forall p, \forall q\neq p.$$

Here "allDiff()" is the CPLEX notation for the "all different" constraint, a global constraint common to most constraint solvers. Given a collection of variables with the same range, the all different constraint says that no two variables in the collection can take the same value.

To put it mildly, I would not be shocked if there is a more efficient (easier to solver) way to write the problem as a CP model.

 

Tournament Scheduling: CPLEX v. CP Optimizer (Part 2)

In my previous post, I described a tournament scheduling problem and discussed my results using both an integer programming model (CPLEX) and a constraint programming model (CP Optimizer) to try to solve it. Here I will present the IP model. (This post will be gibberish unless you have read at least the start of the previous post.)

There are multiple ways to write an integer programming (IP) model for the tournament problem. My initial instinct was to think in terms of what games a pod plays in, which pods it plays with/against and so on, but I fairly quickly changed to thinking in terms of teams rather than pods. With $N=9$ pods and two pods to a team, there are $N(N-1)/2=36$ possible teams, which we can enumerate at the outset. There will be 18 games, each containing two teams, and every team will play exactly once. Each game contains two "slots", one for the team in white jerseys and the other for the team in black jerseys.

In what follows, I will (I hope) stick to the following notation:

• $t$ indexes a team;
• $p$ and $q$ index pods;
• $g$ indexes a game;
• $s$ indexes a slot (and $s'$ is the other slot of the same game);
• $c$ is a jersey color (0 for white, 1 for black).

Since I am using Java, all indexing is zero-based. Slots are numbered so that game 0 has slots 0 (white) and $G$ (black), game 1 has slots 1 (white) and $G+1$ (black), etc., where $G=N(N-1)/4$ is the number of games. I will denote by $T_p$ the set of teams $t$ containing pod $p$.

The model variables are as follows.

• $x_{ts}\in \lbrace 0,1\rbrace$ is 1 if team $t$ plays in slot $s,$ 0 if not.
• $y_{pqs}\in \lbrace 0,1\rbrace$ is 1 if pod $p$ is playing in slot $s$ and is opposed by pod $q.$
• $z_{pg}\in \lbrace 0,1\rbrace$ is the color jersey worn by pod $p$ at the conclusion of game $g$ (regardless of whether or not $p$ played in game $g$).
• $w_{pg}\in \lbrace 0,1\rbrace$ is 1 if pod $p$ changes jersey color going into game $g,$ 0 if not.

The objective is to minimize $\sum_p \sum_g w_{pg}.$ The constraints are the following.

• Every team plays exactly once. $$\sum_s x_{ts} = 1 \quad\forall t.$$
• Every schedule slot is filled exactly once. $$\sum_t x_{ts} = 1 \quad\forall s.$$
• Pods $p$ and $q$ oppose each other with $p$ in slot $s$ if and only if $p$ is playing in $s$ and $q$ is playing in $s'$. $$y_{pqs} \le \sum_{t\in T_p} x_{ts} \quad\forall p, q\neq p, s.$$ $$y_{pqs} \le \sum_{t\in T_q} x_{ts'} \quad\forall p, q\neq p, s.$$ $$y_{pqs} \ge \sum_{t\in T_p} x_{ts} + \sum_{t\in T_q} x_{ts'} - 1 \quad\forall p, q\neq p, s.$$
• Every pair of pods opposes each other exactly twice. $$\sum_s y_{pqs} = 2 \quad \forall p\neq q.$$
• No pod plays consecutive games in different jerseys.$$\sum_{t\in T_p}\left( x_{t,s-1} + x_{t,s'} \right) \le 1 \quad \forall p, \forall s\notin \lbrace 0, G\rbrace.$$
• A pod playing in a game has its jersey color determined by its team's slot. (This has the desirable side effect of preventing two teams containing the same pod from playing against each other.) $$\sum_{t\in T_p} x_{t, g+G} \le z_{pg} \le 1 - \sum_{t\in T_p} x_{t,g} \quad \forall p,g.$$(Note that for any game index $g$, slot $g$ is the white slot in game $g$ and slot $g+G$ is the black slot.)
• A pod's color for any game (playing or not) is the same as its color for the previous game, unless a change occurs. $$z_{p, g-1} - w_{pg} \le z_{pg} \le z_{p, g-1} + w_{pg} \quad\forall p, \forall g \ge 1.$$

In the next post, I will try to articulate my CP model for the problem.

Tournament Scheduling: CPLEX v. CP Optimizer (Part 1)

 A recent question on Mathematics Stack Exchange asked about scheduling $N$ "pods" (players) in a tournament under the following conditions.

• There will be $N(N-1)/4$ games played sequentially (no games in parallel).
• Games pit teams of two pods each against each other. One team wears white and one team wears black.
  
• Each pod partners with every other pod once and plays against every other pod twice.
• No pod can play in consecutive games wearing different jersey colors.

The objective is find a schedule that minimizes the total number of times pods have to change their jersey color.

The question specifies $N=9$. Note that, since there are $N(N-1)/4$ games, a necessary condition for the problem to be feasible is that either $N$ or $N-1$ must be divisible by $4$. That condition is not, however, sufficient. An obvious counterexample is when $N=4$ and there are three games to be scheduled. The first game uses all four teams, as does the second game. Since no pod can be forced to wear different jerseys in consecutive games, all four teams would go into the second game wearing the same colors as in the first game ... which means being in the same teams, violating the rule about pods being teamed together exactly once.

I coded both an integer programming model (using CPLEX) and a constraint programming model (using CP Optimizer) in Java and tried to solve the tournament problem with $N=9$. Since everything is inherently integer and the constraints are more logical than arithmetic (the only real algebra is summing up the number of jersey changes), I had two initial expectations: that CPLEX would provide tighter lower bounds than CPO (because MIP models tend to do better with bounds than CP models); and that CPO would find feasible (and possibly optimal) schedules faster than CPLEX would, since the problem is inherently logic-based (and CP models often do better than MIP models on scheduling problems). I was half right. CPLEX did provide tighter lower bounds than CPO, at least within the time limits I was willing to use, although I don't think either came remotely close to a "tight" lower bound. CPO, however, struggled massively to find feasible schedules while CPLEX did not have too much trouble doing so.

Before going any further, I need to issue three caveats. First, the longest I ran the IP model was 30 minutes and the longest I ran the CP model was an hour. Second, while I am pretty familiar with formulating IP models, I am much less familiar running CP models, so I may have missed opportunities to make the CP model more efficient. Third, while CPLEX gives the user a fair amount of indirect control over the search process (by setting branching priorities, MIP emphasis, how frequently to try certain kinds of cuts and so on), CP Optimizer may offer the user even more flexibility in how to tailor searches I am not yet familiar enough to do anything beyond trying to indicate which variables should be the first candidates for branching (and I'm not sure I got that right).

I'll end this installment with a synopsis of some runs.

• In a 30 minute run using the new setting 5 for the MIP emphasis parameter (stressing use of heuristics to improve the incumbent, at the cost of not paying too much attention to the lower bound), CPLEX found a feasible schedule with 14 jersey changes and a lower bound of 2.97 (a 79% gap). It evaluated somewhere around 18,500 nodes.
  
• In a 30 minute run, CP Optimizer branched over 957 million times but never found a feasible schedule and ended with a best bound of 0.
• Finally, I tried running CPLEX for three minutes (in which it found an incumbent with 19 jersey changes) and then used that incumbent as a starting solution for a one hour run of CP Optimizer. CPO accepted the incumbent solution, did a bit over 1.55 billion branch operations, and failed to improve on it. The best bound was again 0. 

If you want to look at my code (which will make slightly more sense after my next couple of posts, where I will describe the models), it is available from my university GitLab repository.