---
tocdepth: 3
---

# p18 | Timor-Leste Hospital Location

```{seealso}
This problem is sourced from [Ferchtandiker2025](https://github.com/nathan-ferchtandiker/LLMs-For-Optimization-Reformulations).
```

```{note}
- We add implicit assumptions that all sets are non-empty, $v_i, p, M \geq 0$ and $m \leq M$.
```


## Description

Timor-Leste, a country with significant rural populations and challenging terrain, faces difficulties in ensuring equitable access to healthcare. To address this, the government aims to optimize the placement of new hospitals to maximize the number of people with access to healthcare facilities within a reasonable travel distance. The goal is to strategically locate a limited number of new hospitals while retaining all existing facilities, ensuring that as many citizens as possible live within a maximum allowable travel distance (S) from a hospital.

Context and Objectives
Challenge:

Many households, particularly in remote areas, lack access to hospitals within a practical travel distance.

The government can only afford to build p new hospitals due to budget constraints.

Existing hospitals must remain operational to maintain current service levels.

Objective:

Maximize the number of people with access to a hospital within S kilometers.

Prioritize new hospital locations to serve the largest uncovered populations.

Key Components
Facilities and Demand
Existing Hospitals: Already operational; cannot be closed.

Potential New Hospitals: Candidate sites where new hospitals could be built.

Households: Represent clusters of people.

Each household has people needing healthcare access.

travel Distance: Distance from household i to hospital j.

S: Maximum allowable travel distance. Households beyond S from all hospitals are considered "unserved."

Decisions to Make
Hospital Activation: Decide which new potential hospitals to open, with a limit of p new facilities.

Household Assignments: Assign each household i to one hospital within S km, if possible.

Critical Constraints
Existing Hospitals Must Stay Open: All current M hospitals are permanently operational.

Limit on New Hospitals: No more than p new hospitals can be opened.

Travel Distance Compliance: A household i can only be assigned to hospital j if the distance is less than S.

Single Assignment per Household: Each household is assigned to at most one hospital to avoid redundant coverage.

## Formulations
### Formulation `a` (valid)

```{seealso}
This formulation is sourced from [Ferchtandiker2025](https://github.com/nathan-ferchtandiker/LLMs-For-Optimization-Reformulations) (formulation id: efficient).
```

```{note}
- This is the aggregate (efficient) formulation.
```


#### Parameters

| Name | Description | Type | Shape |
|---|---|---|---|
| `nI` | Number of household clusters | integer | *scalar* |
| `m` | Number of existing hospitals | integer | *scalar* |
| `M` | Total number of candidate hospital sites (including existing hospitals) | integer | *scalar* |
| `v` | Population of each household cluster | continuous | `[nI]` |
| `a` | Coverage indicator: 1 if household i is within distance S of hospital j, 0 otherwise | binary | `[nI, M]` |
| `p` | Maximum number of new hospitals that can be opened | integer | *scalar* |


#### Variables

| Name | Description | Type | Shape / Indices |
|---|---|---|---|
| `x` | 1 if hospital j is opened, 0 otherwise | binary | `[M]` |
| `y` | 1 if household i is served by at least one open hospital within distance S, 0 otherwise | binary | `[nI]` |


#### Assumptions

| Description | Formulation | Implicit |
|---|---|---|
| Number of household clusters is positive. | $nI > 0$ | yes |
| Total number of candidate hospital sites is positive. | $M > 0$ | yes |
| Population of each household cluster is non-negative. | $v_i \geq 0 \quad \forall i \in I$ | yes |
| Maximum number of new hospitals is non-negative. | $p \geq 0$ | yes |
| Number of existing hospitals does not exceed total hospital sites. | $m \leq M$ | no |


#### Constraints

- All existing hospitals must remain open.

  $$ x_j = 1 \quad \forall j \in J_0 $$

- At most p new hospitals can be opened.

  $$ \sum_{j \in J_1} x_j \leq p $$

- A household is covered only if at least one open hospital within range is open.

  $$ y_i \leq \sum_{j \in J} a_{ij} x_j \quad \forall i \in I $$

#### Objective

Maximize the total population with access to a hospital within the maximum allowed travel distance.

$$ \max \sum_{i \in I} v_i y_i $$

### Formulation `b` (valid)

```{seealso}
This formulation is sourced from [Ferchtandiker2025](https://github.com/nathan-ferchtandiker/LLMs-For-Optimization-Reformulations) (variation id: inefficient).
```

```{note}
- This is the disaggregate (inefficient) formulation.
```


#### Parameters

| Name | Description | Type | Shape |
|---|---|---|---|
| `nI` | Number of household clusters | integer | *scalar* |
| `m` | Number of existing hospitals | integer | *scalar* |
| `M` | Total number of candidate hospital sites (including existing hospitals) | integer | *scalar* |
| `v` | Population of each household cluster | continuous | `[nI]` |
| `a` | Coverage indicator: 1 if household i is within distance S of hospital j, 0 otherwise | binary | `[nI, M]` |
| `p` | Maximum number of new hospitals that can be opened | integer | *scalar* |


#### Variables

| Name | Description | Type | Shape / Indices |
|---|---|---|---|
| `x` | 1 if hospital j is opened, 0 otherwise | binary | `[M]` |
| `y` | 1 if demand at household i is served by hospital j, 0 otherwise | binary | `[nI, M]` |


#### Assumptions

| Description | Formulation | Implicit |
|---|---|---|
| Number of household clusters is positive. | $nI > 0$ | no |
| Total number of candidate hospital sites is positive. | $M > 0$ | no |
| Population of each household cluster is non-negative. | $v_i \geq 0 \quad \forall i \in I$ | yes |
| Maximum number of new hospitals is non-negative. | $p \geq 0$ | yes |
| Number of existing hospitals does not exceed total hospital sites. | $m \leq M$ | yes |


#### Constraints

- All existing hospitals must remain open.

  $$ x_j = 1 \quad \forall j \in J_0 $$

- At most p new hospitals can be opened.

  $$ \sum_{j \in J_1} x_j \leq p $$

- A hospital can only receive household assignments if it is open.

  $$ \sum_{i \in I} y_{ij} \leq |I| \cdot x_j \quad \forall j \in J $$

- Each household is assigned to at most one hospital.

  $$ \sum_{j \in J} y_{ij} \leq 1 \quad \forall i \in I $$

- Assignment is only permitted to hospitals within the maximum travel distance.

  $$ y_{ij} \leq a_{ij} \quad \forall i \in I,\; \forall j \in J $$

#### Objective

Maximize the total population served by an assigned hospital.

$$ \max \sum_{i \in I} \sum_{j \in J} v_i y_{ij} $$