pyepo.model.grb.tsp

Traveling salesman probelm

Attributes

_HAS_GUROBI

Classes

`unionFind`
`tspABModel`	This abstract class is optimization model for traveling salesman problem.
`tspGGModel`	This class is optimization model for traveling salesman problem based on Gavish–Graves (GG) formulation.
`tspGGModelRel`	This class is relaxation of tspGGModel.
`tspDFJModel`	This class is optimization model for traveling salesman problem based on Danzig–Fulkerson–Johnson (DFJ) formulation and
`tspMTZModel`	This class is optimization model for traveling salesman problem based on Miller-Tucker-Zemlin (MTZ) formulation.
`tspMTZModelRel`	This class is relaxation of tspMTZModel.

Module Contents

pyepo.model.grb.tsp._HAS_GUROBI = True

class pyepo.model.grb.tsp.unionFind(n)

parent

find(i)

union(i, j)

class pyepo.model.grb.tsp.tspABModel(num_nodes)

Bases: pyepo.model.grb.grbmodel.optGrbModel

This abstract class is optimization model for traveling salesman problem. This model is for further implementation of different formulation.

_model

Gurobi model

Type:: GurobiPy model

num_nodes

Number of nodes

Type:: int

edges

List of edge index

Type:: list

num_nodes

nodes

edges

property num_cost: number of cost to be predicted

copy()

A method to copy model

Returns:: new copied model
Return type:: optModel

getTour(sol)

A method to get a tour from solution

Parameters:: sol (list) – solution
Returns:: a TSP tour
Return type:: list

class pyepo.model.grb.tsp.tspGGModel(num_nodes)

Bases: tspABModel

This class is optimization model for traveling salesman problem based on Gavish–Graves (GG) formulation.

_model

Gurobi model

Type:: GurobiPy model

num_nodes

Number of nodes

Type:: int

edges

List of edge index

Type:: list

_getModel()

A method to build Gurobi model

Returns:: optimization model and variables
Return type:: tuple

setObj(c)

A method to set objective function

Parameters:: c (list) – cost vector

solve(): A method to solve model

addConstr(coefs, rhs)

A method to add new constraint

Parameters:

coefs (ndarray) – coeffcients of new constraint
rhs (float) – right-hand side of new constraint

Returns:

new model with the added constraint

Return type:

optModel

relax(): A method to get linear relaxation model

class pyepo.model.grb.tsp.tspGGModelRel(num_nodes)

Bases: tspGGModel

This class is relaxation of tspGGModel.

_model

Gurobi model

Type:: GurobiPy model

num_nodes

Number of nodes

Type:: int

edges

List of edge index

Type:: list

_getModel()

A method to build Gurobi model

Returns:: optimization model and variables
Return type:: tuple

solve()

A method to solve model

Returns:: optimal solution (list) and objective value (float)
Return type:: tuple

relax(): A forbidden method to relax MIP model

getTour(sol): A forbidden method to get a tour from solution

class pyepo.model.grb.tsp.tspDFJModel(num_nodes)

Bases: tspABModel

This class is optimization model for traveling salesman problem based on Danzig–Fulkerson–Johnson (DFJ) formulation and constraint generation.

_model

Gurobi model

Type:: GurobiPy model

num_nodes

Number of nodes

Type:: int

edges

List of edge index

Type:: list

_getModel()

A method to build Gurobi model

Returns:: optimization model and variables
Return type:: tuple

static _subtourelim(model, where): A static method to add lazy constraints for subtour elimination

setObj(c)

A method to set objective function

Parameters:: c (list) – cost vector

solve(): A method to solve model

addConstr(coefs, rhs)

A method to add new constraint

Parameters:

coefs (ndarray) – coeffcients of new constraint
rhs (float) – right-hand side of new constraint

Returns:

new model with the added constraint

Return type:

optModel

class pyepo.model.grb.tsp.tspMTZModel(num_nodes)

Bases: tspABModel

This class is optimization model for traveling salesman problem based on Miller-Tucker-Zemlin (MTZ) formulation.

_model

Gurobi model

Type:: GurobiPy model

num_nodes

Number of nodes

Type:: int

edges

List of edge index

Type:: list

_getModel()

A method to build Gurobi model

Returns:: optimization model and variables
Return type:: tuple

setObj(c)

A method to set objective function

Parameters:: c (list) – cost vector

solve(): A method to solve model

addConstr(coefs, rhs)

A method to add new constraint

Parameters:

coefs (ndarray) – coeffcients of new constraint
rhs (float) – right-hand side of new constraint

Returns:

new model with the added constraint

Return type:

optModel

relax(): A method to get linear relaxation model

class pyepo.model.grb.tsp.tspMTZModelRel(num_nodes)

Bases: tspMTZModel

This class is relaxation of tspMTZModel.

_model

Gurobi model

Type:: GurobiPy model

num_nodes

Number of nodes

Type:: int

edges

List of edge index

Type:: list

_getModel()

A method to build Gurobi model

Returns:: optimization model and variables
Return type:: tuple

solve()

A method to solve model

Returns:: optimal solution (list) and objective value (float)
Return type:: tuple

relax(): A forbidden method to relax MIP model

getTour(sol): A forbidden method to get a tour from solution