7
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Couldn't you just round up the data? $\endgroup$ Nov 24 at 11:09
  • $\begingroup$ @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. $\endgroup$
    – prubin
    Nov 24 at 16:50
  • $\begingroup$ I thought that was the right way to thing as 1.1 rounded up in your eaxmple was called an underestimate. $\endgroup$ Nov 24 at 17:24
  • $\begingroup$ @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. $\endgroup$ Nov 24 at 18:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.