Network design problem with rounded capacity constraints

Question

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.

Answer 1

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.

Answer 2

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).