1

I would like to formulate the following problem:

Each state has multiple counties and each county has multiple municipalities. I have treatment cities and possible control cities (more possible control cities than treatment cities). I want to match each treatment city with the closest control cities (1:1) within the smallest administrative level possible.
So in the first iteration, we try to match each treated city to a control city within the same municipality so that the total distance of matches found is minimized. For the treated cities that could not be matched (as there was no possible control city in the same municipality), we repeat the step with possible control cities in the same county (second iteration). Finally, the remaining non-matching treated cities are matched with control cities in the same state (third iteration).

Furthermore, we restrict matches in each iteration to treat and control cities having the same urbanization status $u$. In the following, the assignment problem ($v$=treated, $c$=control) is shown without the iterative structure and the urbanization constraint. How can I adjust my formulation to take this into account? (I know how to code this but struggle to find the right formulation)

enter image description here

EhsanK
  • 5,864
  • 3
  • 17
  • 54
user13117
  • 11
  • 1
  • By "take this into account" do you mean incorporating both the urbanization constraint and the prioritization of smaller administrative levels? – prubin Jan 23 '24 at 17:28
  • yes, so we only assign a control city to a treatment city if they both have the same urbanization status in all iterations – user13117 Jan 23 '24 at 18:09
  • What I meant was, are you asking for help formulating both the urbanization constraint and the prioritization? – prubin Jan 23 '24 at 18:50

1 Answers1

1

The urbanization part is easy. Fix $x_{vc}=0$ for all $(v,c)$ combinations that do not satisfy the urbanization constraint (either by adding an equation or simply by not including those variables in the model).

For the prioritization part, for each $v$ define three (disjoint) sets. $M_v$ is the set of control cities in the same municipality, $K_v$ is the set of control cities in the same county, and $S_v$ is the set of control cities in the same state. Rewrite your first constraint as $$\sum_v x_{vc} + y_c = 1 \quad\forall c$$ where $y_c$ will equal 1 if $c$ is unassigned and 0 if it is assigned. Now add the following constraints: $$ x_{vc} + y_{c'} \le 1 \quad \forall v, c\in K_v, c'\in M_v$$ and $$ x_{vc} + y_{c'} \le 1 \quad \forall v, c\in S_v, c'\in M_v \cup K_v.$$ The first says that you cannot assign $v$ to a control $c$ in the same county but not city if a there is an unassigned control in the same city. The second says that you cannot assign $v$ to a control $c$ in the same state but not city or county if there is an unassigned control in either the city or county.

I'm assuming here that out-of-state assignments are not allowed at all. If they are, you need one more constraint blocking out-of-state assignments when in-state assignments are possible.

Note that this approach introduces a gaggle of sparse constraints. It is possible to alter them so that you add a smaller number of dense constraints, but I think most solvers prefer many sparse constraints to fewer dense constraints.

ADDENDUM To address Rob's comment, I'll show what I have in mind for the "fewer, denser" option. Replace my first constraint with $$\sum_{c'\in M_v} y_{c'} \le \vert M_v \vert (1-x_{vc}) \quad \forall v, c\in K_v$$ and the second with $$\sum_{c'\in M_v \cup K_v} y_{c'} \le \vert M_v \cup K_v \vert (1-x_{vc})\quad \forall v, c\in S_v.$$ Note that the reduced set of constraints are not only denser but have a "big M" format and hence are likely looser.

prubin
  • 39,078
  • 3
  • 37
  • 104
  • Your last paragraph sounds like you are hinting at https://or.stackexchange.com/questions/6187/how-can-i-strengthen-a-family-of-constraints-in-the-presence-of-a-clique-constra. I would be surprised if the tighter and smaller formulation does worse. Explicitly, replace $x_{vc}$ with $\sum_v x_{vc}$. – RobPratt Jan 23 '24 at 20:32
  • @RobPratt You would need to be careful with the index of summation in your change. Remember that in my formulation $K_v$, $M_v$ and $S_v$ are indexed by $v.$ I edited my answer to indicate what I had in mind. – prubin Jan 23 '24 at 22:38
  • Sorry, I meant to aggregate over $c$, which yields something smaller, denser, and stronger (without big-M). For example, the first one becomes $$\sum_{c\in K_v} x_{vc} + y_{c'} \le 1 \quad \forall v, c' \in M_v$$ – RobPratt Jan 23 '24 at 22:47
  • Yep, that works and is smaller, denser and tighter. – prubin Jan 24 '24 at 04:01
  • thanks for the help but i'm a little puzzled. What is c' in this formulation? And you wrote i should replace the first constraint with the first one your wrote in the ADDENDUM. don't you mean the second one (out of the 3) and the first out of the 3 what rob wrote in his comment? – user13117 Jan 24 '24 at 09:38
  • I meant it replaced the first constraint that I added (the second in my response -- the first in my response was your constraint with a slack variable added). As for $c',$ it indexes control cities whose availability should block the assignments covered in the constraint where it appears. – prubin Jan 24 '24 at 16:47