# Network design problem with rounded capacity constraints

I have a network design problem with complicating capacity constraints which I'm trying to model through a Mixed Integer Programming formulation.

The problem is defined on a directed, incomplete graph $$G(V,A)$$. A binary variable $$x_{uv}^k$$ defines whether commodity $$k\in K$$ is routed via arc $$(u,v)\in A$$. Parameter $$q_k\in \mathbb{R}_{>0}$$ defines the volume of commodity $$k\in K$$. For a subset of nodes $$U\subset V$$, I have the following capacity constraints:

\begin{align} & \sum_{v:(u,v)\in A}\Big\lceil \sum_{k\in K}q_kx_{uv}^k\Big\rceil_{\ell}\leq Q_u & \forall u\in U \end{align} Here, $$Q_u$$ is the capacity of node $$u\in U$$, and $$\lceil\cdot\rceil_{\ell}$$ is a rounding operator that rounds up to the nearest multiple of $$\ell$$. In my application, $$\ell$$ can take the values $$0.5$$ or $$1$$.

The rounding operation makes it troublesome to formulate this constraint. In order to model this, I could associate non-negative integer helper variables $$p_{uv}\in \mathbb{Z}_{\geq 0}$$ with all arcs $$(u,v)\in A$$, and then state the following two constraints: \begin{align} & \sum_{v:(u,v)\in A}p_{uv}\leq \frac{1}{\ell}Q_u & \forall u\in U\\ & \frac{1}{\ell}\sum_{k\in K}q_kx_{uv}^k\leq p_{uv} & \forall (u,v)\in A \end{align}

Although these constraint work in theory, in practice they hinder the scalability of my model. Now I could simply drop the rounding operator and approximate the capacity constraints: \begin{align} & \sum_{v:(u,v)\in A} \sum_{k\in K}q_kx_{uv}^k\leq Q_u & \forall u\in U \end{align} but this creates significant capacity deviations. Here's a simple numerical example. Imagine a node $$u\in U$$ with 10 arcs emanating from this node. When we evaluate the term $$\sum_{k\in K}q_kx_{uv}^k$$ for each of these 10 arcs, we find the values: $$4.04,0.2,0.2,\dots,0.2$$. If we were to evaluate the left hand side of the capacity constraint with $$\ell=0.5$$, we find: $$4.5+0.5+0.5+\dots+0.5=9$$. Without the rounding operator, we would get $$4.04+0.2+0.2+\dots+0.2=5.84$$ which is a significant underestimation. This deviation becomes worse when the number of arcs and commodities increases or when $$\ell$$ is set to 1.

Is there a better way to model these capacity constraints? This is an industrial application: I wouldn't mind to over or underestimate the exact capacity by some margin if this would improve scalability of the model.

• Couldn't you just round up the data? Nov 24, 2021 at 11:09
• @worldsmithhelper If you mean rounding up the individual $q_k$ values, wouldn't that inflate the LHS? For instance, suppose $\ell=0.5$ and an individual arc is carrying three commodities with $q$ values 0.3, 0.6 and 0.2. Their total is 1.1, which rounds up to 1.5. Rounding them individually gives you 0.5 + 1.0 + 0.5 = 2.0. So a feasible solution might look infeasible.
– prubin
Nov 24, 2021 at 16:50
• I thought that was the right way to thing as 1.1 rounded up in your eaxmple was called an underestimate. Nov 24, 2021 at 17:24
• @worldsmithhelper unfortunately, rounding the data, as prubin pointed out, results in significant under-utilization of resources. There's a lot of small $q_k$ values. A commodity with $q_k=0.1$ would be rounded to $0.5$. This potentially overestimates the resources required by a factor of 5. Imagine there are 10 commodities with $q_k=0.1$ that are routed via the same arc $(u,v)$. Before rounding the data, the term $\Big\lceil \sum_{k\in K}q_kx_{uv}^k\Big\rceil_{\ell}$ with $\ell=0.5$ would evaluate to 1, whereas after rounding the data, this term becomes equal to 5. Nov 24, 2021 at 18:13

Not sure what the operation $$\lceil a \rceil_ℓ$$ stands for, thus I will take this as the number, multiple of $$l$$, and greater than or equal to $$a$$.

First, let's focus on the rounding-up part of the $$\lceil a \rceil_ℓ$$ operation. Let $$y_{uv} \in \mathbb{Q}$$ be our $$\lceil \sum_{k \in K} q_k x_{uv}^k \rceil_ℓ$$ $$\forall (u, v) \in A$$, we will have the following constraints.

$$y_{uv} \geqslant \sum_{k \in K} q_k x_{uv}^k$$ $$\forall (u, v) \in A$$ (1)

And then, let's focus on the "multiple of $$ℓ$$" part.

$$y_{uv} = z_{uv} ℓ$$ $$\forall (u, v) \in A$$ (2)

Such that, $$z_{uv} \in \mathbb{N}$$ represents the multiple of $$ℓ$$ composing $$y_{uv}$$.

With these two constraints sets, we then have:

$$\sum_{v : (u, v) \in A} y_{uv} \leqslant Q_u$$ $$\forall u \in U$$ (3)

Case any point is not clear, please let me know.

• I'm not quite sure how your answer answers the original question? Substituting $y_{uv}=z_{uv}\ell$ into $y_{uv}\geq ...$ yields the same constraint as already posted in the original question? Also $\lceil a \rceil_\ell$ is defined in the original question. Dec 5, 2022 at 20:57
• Constraints (1) represent the ceil property of the operation $⌈a⌉ℓ$, while constraints (2) force $y_{uv}$ to be a multiple of ℓ. And yes, substituting $y_{uv} = z_{uv}ℓ$ into $y_{uv} \geqslant ...$ yields the same constraint posted before. Dec 6, 2022 at 10:53
• Joris, if margin of node capacity is the issue, isn't possible to apply rounding to $Q_u$? I mean apply $l$ on the rhs. Dec 6, 2022 at 14:14

While waiting for Joris to say if $$Q_u$$ may be rounded up, I'll take the cue from Matheus Andrade and modify the problem constraints as:

$$q_{uv}^k$$ as the quantity. I'd avoid $$x_{uv}$$ binary because $$q_{uv}^k = 0$$ will mean commodity $$k$$ will not use arc $$(u,v)$$.

$$0 \le z_{uv}^kl -q_{uv}^k$$ (1)

$$z_{uv}^kl -q_{uv}^k \le \epsilon \quad \forall (u,v) \in\ A,\ \forall k \in\ K$$ : (2) where $$z_{uv}^k \ge 0, z_{uv}^k \in\ Z, \ l = 0.5, \ \epsilon \ is \ a \ small \ number \ge 0, \ like \ {l\over 10}$$ Basically constraining to send volume of commodity $$k$$ in multiples of 5, if at all using that arc $$(u,v)$$.

$$\sum_{v:(u,v) \in\ A} \sum_k q_{uv} \le Q_u$$ (3).