Module tsp.tsp_match

TSP - 2-matching and assignment lower bound for the symmetric TSP.

"""
    TSP - 2-matching and assignment lower bound for the symmetric TSP.
"""
import networkx as nx
from docplex.mp.model import Model
from itertools import combinations as combinat
  
#---------------------------------------------------------------------

def __chk_wfunc( problem ):
    """
    Check which version of tsplib95 applies and set the (edge) weight
    function accordingly.
    """
    try:
        _ = problem.wfunc # tsplib95 version before 0.7.1
    except:
        problem.wfunc = problem._wfunc # tsplib95, version 0.7.1
        
#---------------------------------------------------------------------

def assignLB ( problem ):
    """
    Uses networkx min_cost_flow algorithm for computes the assignment
    lower bound. Alternatively, also networkx network simplex algorithm
    could be used instead.

    Parameters:
        **problem** : class  
            The TSP problem object has returned by function load_problem
            of package tsplib95.

    Returns:
        **cost** : int  
            The lower bound (objective value of the assignment problem).  
        **elist** : list of int  
            The list of edges in the assignment.
    """
    # Get the right edge weight function from tsplib95
    __chk_wfunc(problem)
    
    # Solve assignment problem as a minimum-cost network flow problem
    n = problem.dimension
    G = nx.DiGraph()
    for i in problem.get_nodes(): G.add_node(i, demand = -1 )
    for j in problem.get_nodes(): G.add_node(j+n, demand = 1 )
    for i in problem.get_nodes():
        for j in problem.get_nodes():
            if i != j:
                G.add_edge(i,j+n, weight=problem.wfunc(i,j), capacity = n+1 )
    flow = nx.min_cost_flow( G )
    cost = nx.cost_of_flow(G,flow)

    # Retrieve list of edges in the assignment
    elist = [ (e[0],e[1]-n) for e in G.edges if flow[e[0]][e[1]] > 0 ]
    return cost, elist    

#---------------------------------------------------------------------        
        
def twoMatch( problem, fractional=False, log_output=True ):
    """
    Computes the integer or fractional 2-matching lower bound. The 
    (integer) linear program of the 2-matching problem is solved using 
    the Cplex optimizer via docplex

    Parameters:
        **problem** : class  
            The TSP problem object has returned by function load_problem
            of package tsplib95.  
        **fractional** : bool, optional  
            If true, only the linear relaxation of the 2-matching 
            problem is solved. Default=False.  
        **log_output** : bool, optional    
            If true, Cplex sends messages to screen when solving the
            2-matching problem. Default=True.

    Returns:
        **weight** : int or float  
            The (fractional) 2-matching lower bound.  
         **elist** : list of pairs of int  
             The list of edges in the 2-matching and a corresponding.  
         **xvals** : list of floats       
            List of (fractional) solution values. xvals is only
            returned if fractional is true.
    """
    __chk_wfunc( problem )
    model = Model("2-matching")
    
    # List of nodes and edges
    nodes = list(problem.get_nodes())
    edges = list( combinat( nodes, 2 ) )
    
    # Function to access edges incident to a node
    get_edges = lambda node : list( (i,node) for i in nodes if i < node ) \
                             +list( (node,i) for i in nodes if i > node )

    # list of binary (or fractional) edge variables
    if fractional:
        x = model.continuous_var_dict(edges, ub=1.0, name = 'x', key_format = '_%s')
    else:
        x = model.binary_var_dict(edges, name = 'x', key_format = '_%s') 
      
    # Add the objective function to the model
    model.minimize( model.dotf( x, lambda e: problem.wfunc(e[0],e[1]) ) )
    
    # Add degree constraint for each node
    model.add_constraints_( (model.sum(x[e] for e in get_edges(i)) == 2) for i in nodes )
    
    # Solve the model
    sol = model.solve(log_output=log_output)
    
    # Retrieve objective value and edges with positive solution value
    weight = model.objective_value
    xdict = sol.get_value_dict(x,keep_zeros=False)
    edges = list( xdict.keys() )
    
    model.end()
    if fractional: 
        xvals = list( xdict.values() )
        return weight, edges, xvals
    else:
        return weight, edges

Functions

def assignLB(problem)

Uses networkx min_cost_flow algorithm for computes the assignment lower bound. Alternatively, also networkx network simplex algorithm could be used instead.

Parameters

problem : class
The TSP problem object has returned by function load_problem of package tsplib95.

Returns

cost : int
The lower bound (objective value of the assignment problem).
elist : list of int
The list of edges in the assignment.

Expand source code

def assignLB ( problem ):
    """
    Uses networkx min_cost_flow algorithm for computes the assignment
    lower bound. Alternatively, also networkx network simplex algorithm
    could be used instead.

    Parameters:
        **problem** : class  
            The TSP problem object has returned by function load_problem
            of package tsplib95.

    Returns:
        **cost** : int  
            The lower bound (objective value of the assignment problem).  
        **elist** : list of int  
            The list of edges in the assignment.
    """
    # Get the right edge weight function from tsplib95
    __chk_wfunc(problem)
    
    # Solve assignment problem as a minimum-cost network flow problem
    n = problem.dimension
    G = nx.DiGraph()
    for i in problem.get_nodes(): G.add_node(i, demand = -1 )
    for j in problem.get_nodes(): G.add_node(j+n, demand = 1 )
    for i in problem.get_nodes():
        for j in problem.get_nodes():
            if i != j:
                G.add_edge(i,j+n, weight=problem.wfunc(i,j), capacity = n+1 )
    flow = nx.min_cost_flow( G )
    cost = nx.cost_of_flow(G,flow)

    # Retrieve list of edges in the assignment
    elist = [ (e[0],e[1]-n) for e in G.edges if flow[e[0]][e[1]] > 0 ]
    return cost, elist    

def twoMatch(problem, fractional=False, log_output=True)

Computes the integer or fractional 2-matching lower bound. The (integer) linear program of the 2-matching problem is solved using the Cplex optimizer via docplex

Parameters

problem : class
The TSP problem object has returned by function load_problem of package tsplib95.
fractional : bool, optional
If true, only the linear relaxation of the 2-matching problem is solved. Default=False.
log_output : bool, optional
If true, Cplex sends messages to screen when solving the 2-matching problem. Default=True.

Returns

weight : int or float
The (fractional) 2-matching lower bound.
elist : list of pairs of int
The list of edges in the 2-matching and a corresponding.
xvals : list of floats
List of (fractional) solution values. xvals is only returned if fractional is true.

Expand source code

def twoMatch( problem, fractional=False, log_output=True ):
    """
    Computes the integer or fractional 2-matching lower bound. The 
    (integer) linear program of the 2-matching problem is solved using 
    the Cplex optimizer via docplex

    Parameters:
        **problem** : class  
            The TSP problem object has returned by function load_problem
            of package tsplib95.  
        **fractional** : bool, optional  
            If true, only the linear relaxation of the 2-matching 
            problem is solved. Default=False.  
        **log_output** : bool, optional    
            If true, Cplex sends messages to screen when solving the
            2-matching problem. Default=True.

    Returns:
        **weight** : int or float  
            The (fractional) 2-matching lower bound.  
         **elist** : list of pairs of int  
             The list of edges in the 2-matching and a corresponding.  
         **xvals** : list of floats       
            List of (fractional) solution values. xvals is only
            returned if fractional is true.
    """
    __chk_wfunc( problem )
    model = Model("2-matching")
    
    # List of nodes and edges
    nodes = list(problem.get_nodes())
    edges = list( combinat( nodes, 2 ) )
    
    # Function to access edges incident to a node
    get_edges = lambda node : list( (i,node) for i in nodes if i < node ) \
                             +list( (node,i) for i in nodes if i > node )

    # list of binary (or fractional) edge variables
    if fractional:
        x = model.continuous_var_dict(edges, ub=1.0, name = 'x', key_format = '_%s')
    else:
        x = model.binary_var_dict(edges, name = 'x', key_format = '_%s') 
      
    # Add the objective function to the model
    model.minimize( model.dotf( x, lambda e: problem.wfunc(e[0],e[1]) ) )
    
    # Add degree constraint for each node
    model.add_constraints_( (model.sum(x[e] for e in get_edges(i)) == 2) for i in nodes )
    
    # Solve the model
    sol = model.solve(log_output=log_output)
    
    # Retrieve objective value and edges with positive solution value
    weight = model.objective_value
    xdict = sol.get_value_dict(x,keep_zeros=False)
    edges = list( xdict.keys() )
    
    model.end()
    if fractional: 
        xvals = list( xdict.values() )
        return weight, edges, xvals
    else:
        return weight, edges