p15 | Dutch Housing Problem¶

Description¶

The data given in the description below are just examples. The model that has to be developed should contain parameters for these values.

A residential tower consists of several floors. The optimization model has to consider just one of these possibilities. Each floor can have apartments with different areas.

The owner of an apartment can be “corporation”, “investor”, or “private”. There are three important sectors: “social”, “middle”, and “free”. The profit per apartment for the real estate developer is given, and depends on the area of the apartment, the sector, and the owner.

Here are the design restrictions:

Percentage of apartments in “social” sector should be at least a certain percentage of all apartments.

Percentage of apartments in “middle” sector should be at least a certain percentage of all apartments.

There should be a minimum average area requirement for “social” apartments.

There should be a minimum average area requirement for “middle” sector apartments.

There should be a minimum total area of “social” sector apartments owned by corporations.

There should be a minimum total area of “middle” sector apartments owned by corporations.

There should be a minimum total area requirement for “free” sector apartments.

The Corporation cannot buy apartments in the “free” sector.

There should be a minimum Percentage of apartments that go to “investors”.

All apartments on the same floor should be assigned to the same owner class (“corporation”, “investor”, or “private”).

The aim of the real estate developer is to develop a design (i.e., which apartments on which floor, and for each apartment: which sector and which owner) such that the profit for the real estate company is maximized and all restrictions as described above are satisfied.

Formulations¶

Formulation `a` (valid)¶

Parameters¶

Name	Description	Type	Shape
`nI`	Number of sectors	integer	scalar
`nJ`	Number of distinct apartment floor areas	integer	scalar
`nH`	Number of owner classes	integer	scalar
`nV`	Number of floor configurations	integer	scalar
`K`	Total number of floors in the tower	integer	scalar
`R`	Number of apartments with floor area \(j\) in configuration \(v\)	integer	`[nJ, nV]`
`O`	Profit per apartment for sector \(i\), floor area \(j\), and owner \(h\)	continuous	`[nI, nJ, nH]`
`area`	Actual floor area value for area index \(j\)	continuous	`[nJ]`
`m`	Minimum floor area required for each sector \(i\) and owner \(h\)	continuous	`[nI, nH]`
`a`	Minimum fraction of total apartments that must belong to each sector \(i\)	continuous	`[nI]`
`s`	Minimum average floor area required for apartments in each sector \(i\)	continuous	`[nI]`
`o`	Minimum fraction of total apartments that must belong to each owner class \(h\)	continuous	`[nH]`
`iFree`	Index of the free sector	integer	scalar
`hCorp`	Index of the corporation owner class	integer	scalar

Variables¶

Name	Description	Type	Shape / Indices
`x`	Number of floors using configuration \(v\) with owner \(h\)	integer	`[nV, nH]`
`y`	Number of apartments in sector \(i\) with floor area \(j\) and owner \(h\)	integer	`[nI, nJ, nH]`

Assumptions¶

Description	Formulation	Implicit
Number of sectors is positive.	\(nI > 0\)	yes
Number of distinct apartment floor areas is positive.	\(nJ > 0\)	yes
Number of owner classes is positive.	\(nH > 0\)	yes
Number of floor configurations is positive.	\(nV > 0\)	yes
Total number of floors is positive.	\(K > 0\)	yes
\(R\) is non-negative.	\(R_{jv} \geq 0 \quad \forall j \in J, v \in V\)	yes
Area values are non-negative.	\(\text{area}_j \geq 0 \quad \forall j \in J\)	yes
Minimum area requirements are non-negative.	\(m_{ih} \geq 0 \quad \forall i \in I, h \in H\)	yes
Sector fraction lower bounds are non-negative.	\(a_i \geq 0 \quad \forall i \in I\)	yes
Average area lower bounds are non-negative.	\(s_i \geq 0 \quad \forall i \in I\)	yes
Ownership fraction lower bounds are non-negative.	\(o_h \geq 0 \quad \forall h \in H\)	yes
iFree is a valid sector index.	\(0 \leq \text{iFree} < nI\)	no
hCorp is a valid owner index.	\(0 \leq \text{hCorp} < nH\)	no

Constraints¶

Total number of floors equals \(K\).

\[ \sum_{v \in V} \sum_{h \in H} x_{vh} = K \]
Apartment-count consistency: for each area \(j\) and owner \(h\), the total apartments of area \(j\) supplied by chosen configurations equals the total apartments of area \(j\) assigned to any sector.

\[ \sum_{v \in V} R_{jv}\, x_{vh} = \sum_{i \in I} y_{ijh} \quad \forall j \in J,\; h \in H \]
Minimum fraction of total apartments that must be in sector \(i\).

\[ \sum_{j \in J} \sum_{h \in H} y_{ijh} \geq a_i \sum_{l \in I} \sum_{j \in J} \sum_{h \in H} y_{ljh} \quad \forall i \in I \]
Minimum average floor area for sector \(i\).

\[ \sum_{j \in J} \sum_{h \in H} \text{area}_j \times y_{ijh} \geq s_i \sum_{j \in J} \sum_{h \in H} y_{ijh} \quad \forall i \in I \]
Apartments with area below minimum for (sector \(i\), owner \(h\)) must be zero.

\[ y_{ijh} = 0 \quad \forall i \in I,\; j \in J,\; h \in H \text{ with } \text{area}_j < m_{ih} \]
Corporations cannot own free sector apartments.

\[ y_{\text{iFree},j,\text{hCorp}} = 0 \quad \forall j \in J \]
Minimum fraction of total apartments for owner \(h\).

\[ \sum_{i \in I} \sum_{j \in J} y_{ijh} \geq o_h \sum_{i \in I} \sum_{j \in J} \sum_{h' \in H} y_{ijh'} \quad \forall h \in H \]
\(x\) is non-negative. (implicit)

\[ x_{vh} \geq 0 \quad \forall v \in V,\; h \in H \]
\(y\) is non-negative. (implicit)

\[ y_{ijh} \geq 0 \quad \forall i \in I,\; j \in J,\; h \in H \]

Objective¶

Maximize total profit from apartment assignments.

\[ \max \sum_{i \in I} \sum_{j \in J} \sum_{h \in H} O_{ijh}\, y_{ijh} \]

Formulation `b` (valid)¶

Parameters¶

Name	Description	Type	Shape
`nK`	Number of floors in the tower	integer	scalar
`nV`	Number of floor configurations	integer	scalar
`nH`	Number of owner classes	integer	scalar
`nI`	Number of sectors	integer	scalar
`nJ`	Number of distinct apartment floor areas	integer	scalar
`nA`	Maximum number of apartments across all configurations	integer	scalar
`cap`	Number of apartments in configuration \(v\)	integer	`[nV]`
`jApt`	Area index of apartment \(a\) in configuration \(v\) (maps \((v, a)\) to an index in 0..nJ-1)	integer	`[nV, nA]`
`pProfit`	Profit per apartment for sector \(i\), area index \(j\), and owner \(h\)	continuous	`[nI, nJ, nH]`
`area`	Actual floor area value for area index \(j\)	continuous	`[nJ]`
`m`	Minimum floor area required for each sector \(i\) and owner \(h\)	continuous	`[nI, nH]`
`b`	Minimum fraction of total apartments that must belong to each sector \(i\)	continuous	`[nI]`
`s`	Minimum average floor area required for apartments in each sector \(i\)	continuous	`[nI]`
`o`	Minimum fraction of total apartments that must belong to each owner class \(h\)	continuous	`[nH]`
`iFree`	Index of the free sector	integer	scalar
`hCorp`	Index of the corporation owner class	integer	scalar

Variables¶

Name	Description	Type	Shape / Indices
`x`	\(1\) if floor \(k\) uses configuration \(v\) with owner \(h\), \(0\) otherwise	binary	`[nK, nV, nH]`
`y`	\(1\) if apartment \(a\) in configuration \(v\) on floor \(k\) (with owner \(h\)) is assigned to sector \(i\), \(0\) otherwise	binary	`(k, v, h, i, a) for k in range(nK) for v in range(nV) for h in range(nH) for i in range(nI) for a in range(cap[v])`

Assumptions¶

Description	Formulation	Implicit
Number of floors is positive.	\(nK > 0\)	yes
Number of floor configurations is positive.	\(nV > 0\)	yes
Number of owner classes is positive.	\(nH > 0\)	yes
Number of sectors is positive.	\(nI > 0\)	yes
Number of distinct apartment floor areas is positive.	\(nJ > 0\)	yes
cap is non-negative and at most nA for each configuration.	\(0 \leq \text{cap}_v \leq nA \quad \forall v \in V\)	yes
jApt values are valid area indices.	\(0 \leq \text{jApt}_{va} < nJ \quad \forall v \in V,\; a < \text{cap}_v\)	yes
Area values are non-negative.	\(\text{area}_j \geq 0 \quad \forall j \in J\)	yes
Minimum area requirements are non-negative.	\(m_{ih} \geq 0 \quad \forall i \in I,\; h \in H\)	yes
Sector fraction lower bounds are non-negative.	\(b_i \geq 0 \quad \forall i \in I\)	yes
Average area lower bounds are non-negative.	\(s_i \geq 0 \quad \forall i \in I\)	yes
Ownership fraction lower bounds are non-negative.	\(o_h \geq 0 \quad \forall h \in H\)	yes
iFree is a valid sector index.	\(0 \leq \text{iFree} < nI\)	no
hCorp is a valid owner index.	\(0 \leq \text{hCorp} < nH\)	no

Constraints¶

Each floor is assigned exactly one configuration and owner.

\[ \sum_{v \in V} \sum_{h \in H} x_{kvh} = 1 \quad \forall k \in K \]
Each apartment on a chosen floor must be assigned to exactly one sector.

\[ \sum_{i \in I} y_{kvhia} = x_{kvh} \quad \forall k \in K,\; v \in V,\; h \in H,\; a \in A_v \]
Minimum fraction of total apartments that must be in sector \(i\).

\[ \sum_{k} \sum_{v} \sum_{h} \sum_{a \in A_v} y_{kvhia} \geq b_i \sum_{k} \sum_{v} \sum_{h} \sum_{i'} \sum_{a \in A_v} y_{kvhi'a} \quad \forall i \in I \]
Minimum average floor area for sector \(i\).

\[ \sum_{k,v,h,a \in A_v} \text{area}_{j_{va}} \times y_{kvhia} \geq s_i \sum_{k,v,h,a \in A_v} y_{kvhia} \quad \forall i \in I \]
Apartments with area below minimum for (sector \(i\), owner \(h\)) must have zero assignment.

\[ y_{kvhia} = 0 \quad \forall k,v,h,i,a \in A_v \text{ with } \text{area}_{j_{va}} < m_{ih} \]
Corporations cannot own free sector apartments.

\[ y_{kv\,\text{hCorp}\,\text{iFree}\,a} = 0 \quad \forall k \in K,\; v \in V,\; a \in A_v \]
Minimum ownership fraction: total apartments assigned to owner \(h\) meets \(o_h\) times all apartments.

\[ \sum_{k,v} x_{kvh} \times |A_v| \geq o_h \sum_{k,v,h'} x_{kvh'} \times |A_v| \quad \forall h \in H \]

Objective¶

Maximize total profit from apartment assignments.

\[ \max \sum_{k,v,h,i,a \in A_v} p_{i\,j_{va}\,h} \times y_{kvhia} \]

Reformulations¶

Each entry below pairs two formulations of this problem, records whether the second is a reformulation of the first, and gives the parameter map carrying the first formulation’s parameters to the second’s.

a → b (valid)¶

Note

Formulation a describes a configuration by apartment counts \(R_{jv}\); formulation b indexes apartments individually.
\(\text{jApt}\) is determined only up to the order of a configuration’s apartments, which are interchangeable. The Python listing fixes the canonical choice: area indices in ascending order of \(j\). Entries at \(a \geq \text{cap}_v\) pad the row out to \(nA\) and are never referenced by formulation b.

Parameter map

Name	Definition in terms of `a`
`nK`	\(nK = K\)
`nV`	\(nV = nV\)
`nH`	\(nH = nH\)
`nI`	\(nI = nI\)
`nJ`	\(nJ = nJ\)
`cap`	\(\text{cap}_v = \sum_{j \in J} R_{jv} \quad \forall v \in V\)
`nA`	\(nA = \max_{v \in V} \text{cap}_v\)
`jApt`	\(\|\{a < \text{cap}_v : \text{jApt}_{va} = j\}\| = R_{jv} \quad \forall j \in J,\; v \in V\)
`pProfit`	\(p_{ijh} = O_{ijh}\)
`area`	\(\text{area}_j = \text{area}_j\)
`m`	\(m_{ih} = m_{ih}\)
`b`	\(b_i = a_i\)
`s`	\(s_i = s_i\)
`o`	\(o_h = o_h\)
`iFree`	\(\text{iFree} = \text{iFree}\)
`hCorp`	\(\text{hCorp} = \text{hCorp}\)

p15 | Dutch Housing Problem¶

Description¶

Formulations¶

Formulation a (valid)¶

Parameters¶

Variables¶

Assumptions¶

Constraints¶

Objective¶

Formulation b (valid)¶

Parameters¶

Variables¶

Assumptions¶

Constraints¶

Objective¶

Reformulations¶

a → b (valid)¶

Formulation `a` (valid)¶

Formulation `b` (valid)¶