1
$\begingroup$

I have a variation the shortest path problem, formulated as an ILP. The system model is as follows:

  • There is a connected digraph consisting of 20 nodes, with each link having an associated weight delay which is a float. The graph is modeled as a python networkx object as follows:

    g = nx.DiGraph(nx.barabasi_albert_graph(20, 2))
    for u, v in g.edges:
        g[u][v]['delay'] = random.uniform(50, 1000)  # uS
    
  • There are multiple source-destination pairs and each pair has an associated 'demand' in terms of delay. The problem is modeled in python PuLP and solved using Gurobi solver.

    # get cost
    delay_d = nx.get_edge_attributes(self.graph, 'delay')
    
    
    # get links
    links = []
    for i, j in self.graph.edges:
        links.append((i, j))
    
    # instantiate the problem
    prob = pulp.LpProblem("Shortest Path Problem", pulp.LpMinimize)
    
    # create binary variables to state a link is chosen on shortest path
    var_dict = {}
    for flow_name in self.list_of_flows:
        for (i, j) in links:
            var = pulp.LpVariable('x_(%s,%s)_%s' % (i, j, flow_name), cat=pulp.LpBinary)
            var_dict[(i, j, flow_name)] = var
    
    # create slack variables for every flow
    delay_slack = {}
    for flow_name in self.list_of_flows:
        delay_slack[flow_name] = pulp.LpVariable('d_%s' % flow_name, lowBound=0.0, cat=pulp.LpContinuous)
    
    # formulate the objective
    prob += pulp.lpSum([pulp.lpSum([delay_d[(i, j)] * var_dict[(i, j, flow_name)] for (i, j) in links])
                        for flow_name in self.list_of_flows ]) \
            + pulp.lpSum([1000 * delay_slack[flow_name] for flow_name in self.list_of_flows])
    
    # formulate the constraints
    for flow_name, flow in self.list_of_flows.items():
        # conservation of flow constraints
        for node in self.graph.nodes:
            if node == flow['source']:
                prob += pulp.lpSum([var_dict[(i, j, flow_name)] for (i, j) in links if i == node]) - \
                        pulp.lpSum([var_dict[(j, i, flow_name)] for (j, i) in links if i == node]) == 1
            elif node == flow['target']:
                prob += pulp.lpSum([var_dict[(i, j, flow_name)] for (i, j) in links if i == node]) - \
                        pulp.lpSum([var_dict[(j, i, flow_name)] for (j, i) in links if i == node]) == -1
            else:
                prob += pulp.lpSum([var_dict[(i, j, flow_name)] for (i, j) in links if i == node]) - \
                        pulp.lpSum([var_dict[(j, i, flow_name)] for (j, i) in links if i == node]) == 0
    
        # delay constraint
        prob += pulp.lpSum([var_dict[(i, j, flow_name)] * delay_d[(i, j)]
                            for (i, j) in links]) - delay_slack[flow_name] <= flow['qos']['delay']
    
    # solve the optimization problem
    prob.solve(pulp.GUROBI_CMD(msg=0))
    

There are no issues with the solution and correct results are obtained. However, when I calculated the runtime, the results seem to be linear.

Runtime of ILP vs input size

Now, I know that if an ILP satisfies the property of unimodularity, then the LP relaxation gives integer solution. Thus such an ILP can be solved in polynomial time using methods such as simplex.

However, if we look at the delay constraints, the coefficients of LHS are not integers, nor is the RHS integer. Thus it seems unimodularity property is not satisfied. Hence, shouldn't the runtime be exponential?

Can anyone explain why the runtime graph is linear?

$\endgroup$
3
$\begingroup$

I will try to answer to your question with an example.
Consider the following time complexity: $f(n)=2^\frac{n}{1000}$.

It is clearly exponential in $n$, but look at the plot.

For $n \in [0,80]$:

enter image description here

From this perspective it looks constant, right?

For $n \in [0, 1.5 \cdot 10^4]$:

enter image description here

From this perspective everything changes.

What I want to show, is that inferring the complexity just looking at the runtime with different inputs size is not possibile.

$\endgroup$
3
$\begingroup$

Remember that NP-hardness is about worst-case intractability. For example, it is perfectly possible you can solve even large ILP instances quickly. If and when this happens, the instance has some structure the ILP solver is able to exploit to find a solution quickly.

$\endgroup$

Your Answer

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

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