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$ Commented Nov 24, 2021 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
    Commented Nov 24, 2021 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$ Commented Nov 24, 2021 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$ Commented Nov 24, 2021 at 18:13

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Dec 5, 2022 at 20:57
  • $\begingroup$ 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. $\endgroup$ Commented Dec 6, 2022 at 10:53
  • $\begingroup$ 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. $\endgroup$ Commented Dec 6, 2022 at 14:14
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.