<jupyter_start><jupyter_text>6. Integer (ILP), mixed programming (MILP) and Branch and Bound (B and B)         <NAME>, Lucami, FE      Contact: prof. dr. <NAME>, <EMAIL>, skype=akosir_sid  1   6. Integer (ILP) in mixed programming (MILP)   Goals  ■ Intro, goal:- Goals    - Know the formulation and relation to LP    - Know algorithmic specifics    - Cases in  TC- Naive solution:    - First solve LP for real numbers and then rounding?    - Wrong: not optimal, even not feasible        - Why limit to integers?    - Logical variables    - Set membership like a link on a path 2   6. Integer (ILP), mixed programming (MILP) and Branch and Bound (B and B)   Sections  ■ Sections6.1. Definition, solvability, algorithm■ Integer and Mixed-integer programming definition $\large{*}$■ Theory: total unimodularity■ ILP algorithm6.2 ILP in ICT examples■ Some ILP in ICT tasks $\large{*}$■ Service cost problem■ Elastic optical network optimization problem6.3. Algorithm Branch and bound ■ B&B: an umbrela of algorithms■ B&B solution of a MILP problem 3   6. Integer (ILP), mixed programming (MILP) and Branch and Bound (B and B)   6.1. Definition, solvability, algorithm  6.1. Definition, solvability, algorithm■ Integer and Mixed-integer programming definition■ Theory: total unimodularity■ ILP algorithm 4   6. Integer (ILP), mixed programming (MILP) and Branch and Bound (B and B)   6.1. Definition, solvability, algorithm  ■ Definition of integer programming- Definition$$ \matrix{ & & argmax_x w^\top.x \cr  & s.t. & \cr & & A.x \leq b \hfill \cr & & x\in ℕ \hfill} $$- Mixed examples:    - Mixed integer linear programming    - Zero – one linear programming: logical variables, typically related to set membership- Why?    - Real cases require it 5   6. Integer (ILP), mixed programming (MILP) and Branch and Bound (B and B)   6.1. Definition, solvability, algorithm  ■ Theory: total unimodularity- Totally unimodular matrix $A$:    - Unimodular matrix : integers, $\det(A)=\pm 1$. Equivalent: matrix has integer inverse;    - Totally unimodular matrix: any non-singular submatrix is unimodular. Consists of entries $−1,0,1$.- If a matrix $A$ is totally unimodular:    - Basic feasible solutions are integers    - Simplex algorithm results in integer solutions- How do we check total unimodualrity:    - Paper: <NAME>. A decomposition theory for matroids. V. Testing of matrix total unimodularity, J. Comb. Theory, Ser. B 49, 241-281, 1990.    - Algorithm: $O((𝑛+𝑚)^5)$- If a matrix A is totally unimodular:    - Basic feasible solutions are integers    - Simplex algorithm results in integer solutions  6   6. Integer (ILP), mixed programming (MILP) and Branch and Bound (B and B)   6.1. Definition, solvability, algorithm  ■ Theory: total unimodularity (2) Total unimodularity is only a sufficient condition, not a necessary one. See cases bellow.  Case 1:$$ w = [2, 4, 3]^\top, \qquadA_1 = \left[\matrix{    1  & -1  &  0 \cr     -1 &  0  &  1 \cr    1  &  1  & -1}\right], \qquad b = [3, 2, 4]^\top $$- is $A_1$ unimodular? No.- is the solution intiger? Yes: $x^* = [12, 9, 17]$ Case 2:$$ w = [2, 4, 3]^\top, \qquadA_2 = \left[\matrix{    1  & -1  &  0 \cr     -1 &  1  &  1 \cr    1  &  1  & -1}\right], \qquad b = [3, 2, 4]^\top $$- is $A_1$ unimodular? No.- is the solution intiger? No: $x^* = [7.5, 4.5, 8]$ 7   6. Integer (ILP), mixed programming (MILP) and Branch and Bound (B and B)   6.1. Definition, solvability, algorithm  ■ Algorithms solving ILP- First choice: branch and bound- Simplex algorithm for totally unimodular matrix A - rarely useful on our domain- Special algorithms for special cases 7   6. Integer (ILP), mixed programming (MILP) and Branch and Bound (B and B)   6.2 ILP in ICT examples  6.2 ILP in ICT examples■ Selected task of ILP v TK■ Service cost problem■ Elastic optical network optimization problem 8   6. Integer (ILP), mixed programming (MILP) and Branch and Bound (B and B)   6.2 ILP in ICT examples  ■ Selected task of ILP v TK - network design  - service prising problems - covering problems - Boolean satisfability problem" - Travel salesman problem  9   6. Integer (ILP), mixed programming (MILP) and Branch and Bound (B and B)   6.2 ILP in ICT examples  ■ Optimal TC service pricing problem  (1)- Paper: <NAME> and <NAME> and <NAME>: Mixed Integer Programming model for pricing in telecommunication, 2011.- Yield management- Service cost as a network regulator: dependent on the traffic load- The traffic: 10   6. Integer (ILP), mixed programming (MILP) and Branch and Bound (B and B)   6.2 ILP in ICT examples  ■ Optimal TC service pricing problem (2) - Input data:    - Number of time slots: $n_T$    - Number of load levels: $n_I$    - Load thresholds: $L_i$    - The cost of last interval of the previous day: $p_{-1}$     - Time dependent load function: $\rho(k, p_{k-1})$, $k$ time index    - Time dependent demand function: $D(k, p_k)$    - Time dependent revenue function: $R(k, p_k)$    - Variables:    - Price assigned to time slot: $p_k\in [P_{min}, P_{max}]$    - Price assigned to load level: $[L_{i-1}, L_i]$: $r_i\in [P_{min}, P_{max}]$, $i$ index of load level;    - Boolean variable $\beta_i^k=1$ if load at time 𝑘 is in load level $i$ and $0$ otherwise    - Load $\alpha_i^k$: variable equals to load at $k$ if it is in load level $k$, $0$ otherwise. 11   6. Integer (ILP), mixed programming (MILP) and Branch and Bound (B and B)   6.2 ILP in ICT examples  ■ Optimal TC service pricing problem (3)- Problem$$ \matrix{ & & argmax_{p_k, r_i} \sum_{k=1}^{n_T-1} R(k, p_k) \cr  & s.t. & \cr}$$        $\sum_{i=0}^{n_I} \alpha_i^k = \rho(k, p_{k-1})$, $\forall k$     (1)          $\beta_i^k L_{i-1} \leq \alpha_i^k \leq \beta_i^k L_i$, $\forall i, k$     (2)          $\sum_{i=0}^{n_I} \beta_i^k = 1$, $\forall k$      (3)           $(\beta_i^k-1)M \leq p_k - r_i \leq (1-\beta_i^k)M$, $\forall i, k$      (4)           $\beta_{n_I}^{k-1} + \beta_{n_I}^k \leq 1$, $\forall k\ne 0$      (5)           $\beta_i^k\in\{0, 1\}$, $\forall i, k$      (6)           $\alpha_i^k \geq 0$, $\forall i, k$      (7)           $r_i \in [P_{min}, P_{max}]$, $\forall i$, $p_k \in [P_{min}, P_{max}]$, $\forall k$      (8)     12   6. Integer (ILP), mixed programming (MILP) and Branch and Bound (B and B)   6.2 ILP in ICT examples  ■ Optimal TC service pricing problem (4) - Explanation:    - Cost function: revenue per time period    - (1): Constants $\alpha_i^k$ are equal to true loads    - (2): It limits the load to the predefined interval;    - (3): At each time exactly one load interval is selected;    - (4): Loads are set to true values: $p_k=r_i$;    - (5): Prevents congestion in two consequent intervals;    - (6): Binary – logical variable $\beta_i^k$;    - (7): Loads are nonnegative     - (8): Costs are limited 13   6. Integer (ILP), mixed programming (MILP) and Branch and Bound (B and B)   6.2 ILP in ICT examples  ■ Optimal TC service pricing problem (5)- Model of load and revenue:    - Load goes down with increasing price: $\rho(k, p_{k-1}) = d_k - c_k p_{k-1}$    - Revenue $R(k, p_k) = D(p_k) p_k = b_k p_k - a_k p_k^2$- Predefine time intervals and levels of load:    - Time intervals: $[0,t_0=6]$, $[6,t_1=18]$, $[18,t_2=24]$;    - Intervals of load: $[0, L_1=10]$, $[10, L_2=30]$, $[30, L_3=50]$, $[50, \infty)$;- Model parameters:       inter. $k$      $a_k$       $b_k$      $c_k$      $d_k$         $0$    $10$     $20$    $6$    $12$        $1$    $15$     $25$    $8$    $16$        $2$    $12$     $22$    $7$    $11$  - Price limits: $P_{min}=30$, $P_{max}=90$- „Big M“ $M=10000$ 14   6. Integer (ILP), mixed programming (MILP) and Branch and Bound (B and B)   6.2 ILP in ICT examples  ■ Optimal TC service pricing problem (6)- Results:       $p_0=90$    $p_1=90$     $p_2=90$        $r_0=90$    $r_1=90$     $r_2=90$   15   6. Integer (ILP), mixed programming (MILP) and Branch and Bound (B and B)   6.2 ILP in ICT examples  ■ Problem of optimisation of elastic optical network  (1)- Paper: Pages et. al: Optimal Route, Spectrum, and Modulation Level Assignment in Split-Spectrum-Enabled Dynamic Elastic Optical Networks, 2014.- What is elastic optical network:    - Split Spectrum approach, SSA    - Frequency Slots, FS    - Channels: sequence of contiguous FS with a given modulation    - Several modulations: different speeds, transmission reach etc,     - Each new request $\to$ new resource allocation - Route, spectrum, and modulation level assignment, RMSLA    - Allocation of frequency slots    - Allocation of channels and modulations 16   6. Integer (ILP), mixed programming (MILP) and Branch and Bound (B and B)   6.2 ILP in ICT examples  ■ Problem of optimisation of elastic optical network (2)- Simple example of the network    - Network graph $G=(V, E)$, $V=\{1,2,3,4,5\}$, $E=\{(12), (13), (23), (24), (34), (35), (45)\}$    - Source, sink: $s=N_1$, $t=N_5$    - Request: $s_d\to t_d$, $R_d = 50$ Gbit/s    - Optimization criteria:        - Minimal resources allocated        - Minimal number of spectral gaps 17   6. Integer (ILP), mixed programming (MILP) and Branch and Bound (B and B)   6.2 ILP in ICT examples  ■ Problem of optimisation of elastic optical network (3)- Frequency slots, FS    - $F_w$: spectral width of a FS, typically $6,25 GHz$ or $12,5 GHz$, our case $F_w=10 GHz$    - $G$: guard band size, we assume $G=8GHz$ 18   6. Integer (ILP), mixed programming (MILP) and Branch and Bound (B and B)   6.2 ILP in ICT examples  ■ Problem of optimisation of elastic optical network (4)- Modulations (in [GHz])    - $R_m$: modulation $m$ bit rate    - $B_m$: spectral width of modulation $m$    - $S_m=⌈\frac{B_m+G}{F_w}⌉$: number of required FS of modulation $m$    - $TR_m$: Modulation  $m$ transmission reach       $m$      $R_m$[Gb/s]       $B_m$[GHz]      $TR_m[km]$      $S_m$         $1$    $25$     $12$    $20$    $2$        $2$    $50$     $14$    $14$    $3$        $3$    $75$     $10$    $10$    $1$  - Limitation:   - Bit rate: $R_d\leq \sum_{i=1}^H R_{m_i}$   19   6. Integer (ILP), mixed programming (MILP) and Branch and Bound (B and B)   6.2 ILP in ICT examples  ■ Problem of optimisation of elastic optical network (5)- A list of possible paths $P_d$ and    - $h_p$: number of hops $p\in P_d$    - $l_p$: total cost of path $p$,          $p_{id}$      $p$       $l_p$      $h_p$         $1$    $(1245)$     $13$    $2$        $2$    $(12345)$     $14$    $3$        $3$    $(1235)$     $12$    $2$        $4$    $(1345)$     $13$    $2$        $4$    $(135)$     $11$    $1$  - Channels:    - All possible channels of a path $p$ are denoted by $C_p$ 20   6. Integer (ILP), mixed programming (MILP) and Branch and Bound (B and B)   6.2 ILP in ICT examples  ■ Problem of optimisation of elastic optical network (6)- Current occupation of frequency slots FS by paths    - Channels occupies the same FS along the path    - A star $*$ marks occupied channels denoted by $F_p^u$. Vacant FSs are $F_p^u$       $p_{id}$      $1$       $2$      $3$      $4$       $5$      $6$      $7$       $8$      $9$      $10$          $1$    \*    \*                                              $2$            \*                                          $3$                      \*    \*    \*                        $4$                      \*    \*                            $5$    \*    \*                                         21   6. Integer (ILP), mixed programming (MILP) and Branch and Bound (B and B)   6.2 ILP in ICT examples  ■ Problem of optimisation of elastic optical network (7)- Current occupation of frequency slots FS by links    - Numbers are path indices, no number means vacant FS       $p$      $e,FS$      $1$       $2$      $3$      $4$       $5$      $6$      $7$       $8$      $9$      $10$          $1,2,3$    12    1    1    2          3    3    3                        $4,5$    13    5    5              4    4                            $2,3$    23                  2    3    3    3                    $1$    24    1    1                                              $2,4$    34            2          4    4                            $3,5$    35    5    5              3    3    3                        $1,2,4$    45    1    1    2          4    4                       22   6. Integer (ILP), mixed programming (MILP) and Branch and Bound (B and B)   6.2 ILP in ICT examples  ■ Problem of optimisation of elastic optical network (8)- Feasible modulations - available to be assigned?       $p_{id}$      $m=1, S_m=2$       $m=2, S_m=3$      $m=3, S_m=1$         $1$    $7-8,8-9,9-10$     $7-9,8-10$    $7-7,8-8,9-9,10-10$        $2$    $7-8,8-9,9-10$     $7-9,8-10$    $7-7,8-8,9-9,10-10$        $3$    $7-8,8-9,9-10$     $7-9,8-10$    $7-7,8-8,9-9,10-10$        $4$    $6-7,7-8,8-9,9-10$     $6-8,7-9,8-10$    $6-6,7-7,8-8,9-9,10-10$        $5$    $7-8,8-9,9-10$     $7-9,8-10$    $7-7,8-8,9-9,10-10$   23   6. Integer (ILP), mixed programming (MILP) and Branch and Bound (B and B)   6.2 ILP in ICT examples  ■ Problem of optimisation of elastic optical network (9)- Constraints and limitations    - Capacity: $R_d \leq \sum_{i=1}^H R_{m_i}$      - Each modulation occupies contiguous FS    - Channels occupies the same FS along the path    - There is upper limit of number of elastics paths $FL_{max}$    - Upper limit on number pf parts: $H_{max}$    - Upper limit on number of involved paths: $L_{max}$ 24   6. Integer (ILP), mixed programming (MILP) and Branch and Bound (B and B)   6.2 ILP in ICT examples  ■ Problem of optimisation of elastic optical network (10)- Variables, notations    - $x_{p,x}$, $p\in P$, $c\in C_p$: binary indicator od paths and channels    - $y_p$,  $p\in P$: binary indicator of path    - $z_{p,f}$, $p\in P$, $f\in FS$: binary indicator of FS    - $P_p$, $p\in P$: Number of parts of a path    - $T_p$: Number of gaps in FS on a path 𝑝∈𝑃    - $w_{p,f, f+1}$: slack variables    - $A$: difference between the requested bit rate and the allocated bit rate. 25   6. Integer (ILP), mixed programming (MILP) and Branch and Bound (B and B)   6.2 ILP in ICT examples  ■ Problem of optimisation of elastic optical network (11)- MILP formulation for general network    - Cost function$$ \matrix{c(x_{p,c}) &=& \alpha\frac{1}{H_{max}|P_d|} \sum_{p\in P_d} h_p P_p  \;+\; \beta\frac{1}{|F||P_d|} \sum_{p\in P_d} h_p T_p  \cr && + \quad \gamma\frac{1}{|C|}\sum_{p\in P_d} h_p \sum_{c\in C_p} S_c(1+\varepsilon f_c) x_{p,c} \;+\; \delta\frac{A}{max \{R_m\}}} $$Optimization task: $$ argmin_x c(x) $$ 26   6. Integer (ILP), mixed programming (MILP) and Branch and Bound (B and B)   6.2 ILP in ICT examples  ■ Problem of optimisation of elastic optical network (12)- Constraints:    - Capacity:     $$ R_d \leq \sum_{p\in P_d} \sum_{c\in C_p} R_c x_{p,c} $$    - Difference between the requested bit rate and the allocated bit rate:      $$ A = \sum_{p\in P_d} \sum_{c\in C_p} R_c x_{p,c} - R_d $$    Number of channels is limited:    $$ x_{p,c} \leq y_p $$    $$ \sum_{p\in P_d} y_p \leq L_{max} $$             27   6. Integer (ILP), mixed programming (MILP) and Branch and Bound (B and B)   6.2 ILP in ICT examples  ■ Problem of optimisation of elastic optical network (13)- Constraints (cont.)    - Limit on number of parts:    $$ \sum_{p\in P_d} P_p \leq H_{max}, FL_{max} $$    - Each channel is used at most ones:     $$ \sum_{p\in P_d} \sum_{c\in C_f} x_{p,c} \leq 1 $$    - Number of parts:     $$ P_p = \sum_{c\in C_p} x_{p,c} $$ 28   6. Integer (ILP), mixed programming (MILP) and Branch and Bound (B and B)   6.2 ILP in ICT examples  ■ Problem of optimisation of elastic optical network (14)- Constraints (cont.)    - Number of spectral gaps:    $$ T_p = \sum_{i=1}^{|F|} z_{p,i} - \sum_{i=1}^{|F|-1} w_{p,i,i+1} $$    - Occupied frequency slots:    $$ z_{p,f} = 1, \quad \forall p\in P, f\in F_p^u. $$    - Vacant frequency slots:    $$ z_{p,f} = \sum_{c\in C_f} x_{p,f}, \quad \forall p\in P, f\in F\setminus F_p^u. $$    - Slack variables:    $$ w_{p,i,i+1} \leq z_{p,i}, z_{p,i+1} $$    $$ w_{p,i,i+1} \geq z_{p,i} + z_{p,i+1} - 1 $$ 29   6. Integer (ILP), mixed programming (MILP) and Branch and Bound (B and B)   6.2 ILP in ICT examples  ■ Problem of optimisation of elastic optical network (15)- Problem type:     - Mixed integer linear programming, MILP)- How to do it:    - Case study     - Automated of file formulation 30   6. Integer (ILP), mixed programming (MILP) and Branch and Bound (B and B)   6.2 ILP in ICT examples  ■ Problem of optimisation of elastic optical network (15)- Problem type:     - Mixed integer linear programming, MILP)- How to do it:    - Case study     - Automated of file formulation 30   6. Integer (ILP), mixed programming (MILP) and Branch and Bound (B and B)   6.3. Algorithm Branch and bound  6.3. Algorithm Branch and bound ■ B&B: an umbrela of algorithms■ B&B solution of a MILP problem 31   6. Integer (ILP), mixed programming (MILP) and Branch and Bound (B and B)   6.3. Algorithm Branch and bound  ■ B&B: an umbrela of algorithms- not a single algorithm, only a scheme Steps:For the optimisation task $OpT = (\Omega, \Phi, c, F)$1. Load the optimisation problem $OpT$ 2. Compute lower bound $L=l(OpT)$ and upper bound $U=u(OpT)$3. Branch the optimisation problem $OpT = OpT1 + OpT2$4. Comput lower bounds $l(OpT1)$, $l(OpT2)$ and upper bounds $u(OpT1)$ and $u(OpT2)$5. Update lower and upper bounds     - update lower bound: $L = \min(l(OpT1), l(OpT2))$     - update upper bound: $U = \max(u(OpT1), u(OpT2))$    - if $U_2 - L_2 < \varepsilon$, terminate6. Go to step 3 with $OpT1$ and with $OpT2$ separatelly  32<jupyter_code># A simple implementation of B&B: project pybnb 
#  https://pypi.org/project/pybnb/

# Required installs
#  pip install pybnb
#  pip install mpi4py


import pybnb

class Simple(pybnb.Problem):
    def __init__(self):
        self.bounds = [0.0,1.0]
    def sense(self):
        return pybnb.minimize
    def objective(self):
        return round(self.bounds[1] - self.bounds[0], 3)
    def bound(self):
        return -(self.bounds[1] - self.bounds[0])**2
    def save_state(self, node):
        node.state = self.bounds
    def load_state(self, node):
        self.bounds = node.state
    def branch(self):
        L, U = self.bounds
        mid = 0.5 * (L + U)
        for l,u in [(L,mid), (mid,U)]:
            child = pybnb.Node()
            child.state = (l,u)
            yield child
problem = Simple()
results = pybnb.solve(problem,
                      absolute_gap=1e-9)
results.bound<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.13545557901575442, 'fraction_numerical': 0.04049591251150452, 'mean_word_length': 2.464366091522881, 'pattern_counts': {'":': 0, '<': 13, '<?xml version=': 0, '>': 12, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 25, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '393786', 'license': 'MIT', 'n_tokens_mistral': 6716, 'n_tokens_neox': 6276, 'n_words': 2452, 'path': 'AKosir-OPvTK-Lec06_ILPandMILPandBandB_ANGL.ipynb', 'repo_name': 'andrejkk/OPvTK', 'size': '18541'}