# 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 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. Nov 24 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 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 at 18:13