I need help with this integer programming problem

50 Views Asked by At

I do not know how to solve this integer programming problem. $$\min_{w_{i,j}} \sum_{i=1}^{N}\sum_{j=1,j \neq i}^{N} w_{i,j}$$ $$s.t. \sum_{j=1,j \neq i}^{N} w_{i,j} \geq L, \forall i \in \left[ N \right]$$ $$w_{i,j} = w_{j,i}, \forall i \in \left[ N \right], j \in \left[ N \right], i \neq j$$ $$w_{i,j} \in \left[ S \right], \forall i \in \left[ N \right], j \in \left[ N \right], i \neq j$$

$L$ is a positive integer, $\left[ N \right]$ is a set of positive integers and $\left[ N \right] = \left\{ 1, 2, \dots, N \right\}$, $\left[ S \right]$ is a set of non-negative integers and $\left[ S \right] = \left\{0, 1, \dots, N \right\}$

1

There are 1 best solutions below

0
On

You can use an integer programming package (e.g. mips in python) to solve the problem, first you need to define the variables in order to express the objective function and the constraints and define the parameter ($N, L$) values:

from sys import stdout
from mip import Model, xsum, INTEGER

N = 10
L = 2

model = Model()

w = [[model.add_var('w({},{})'.format(i, j), var_type=INTEGER, lb=0, ub=N)
      for j in range(N)] for i in range(N)]

model.objective = xsum(w[i][j]*(i!=j) for i in range(N) for j in range(N))

for i in range(N):
    model.add_constr(xsum(w[i][j]*(i!=j) for j in range(N)) >= L)
    
for i in range(N):
    for j in range(N):
        model.add_constr(w[i][j] == w[j][i])
    
model.optimize()

if model.num_solutions:
    stdout.write('\n')
    for i, v in enumerate(model.vars):
        stdout.write(str(int(v.x)))
        if i % N == N-1:
            stdout.write('\n')

# solution
# 0000000020
# 0000002000
# 0000100100
# 0000010001
# 0010000100
# 0001000001
# 0200000000
# 0010100000
# 2000000000
# 0001010000

The above solution to be interpreted as $w_{1,9}=2$, $w_{2,7}=2$, $w_{3,5}=w_{3,8}=1$ etc.