pyepo.model.copt.tsp

Traveling salesman problem

Attributes

num_nodes

Classes

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

Module Contents

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

Bases: pyepo.model.copt.coptmodel.optCoptModel

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

_model

COPT model

Type:: COPT model

num_nodes

Number of nodes

Type:: int

edges

List of edge index

Type:: list

num_nodes

nodes

edges

property num_cost: number of costs 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.copt.tsp.tspGGModel(num_nodes)

Bases: tspABModel

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

_model

COPT model

Type:: COPT model

num_nodes

Number of nodes

Type:: int

edges

List of edge index

Type:: list

_getModel()

A method to build COPT model

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

setObj(c)

A method to set the 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) – coefficients 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.copt.tsp.tspGGModelRel(num_nodes)

Bases: tspGGModel

This class is relaxation of tspGGModel.

_model

COPT model

Type:: COPT model

num_nodes

Number of nodes

Type:: int

edges

List of edge index

Type:: list

_getModel()

A method to build COPT 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.copt.tsp.tspDFJModel(num_nodes)

Bases: tspABModel

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

_model

COPT model

Type:: COPT model

num_nodes

Number of nodes

Type:: int

edges

List of edge index

Type:: list

class _SubtourCallback(x, n, edges)

Bases: coptpy.CallbackBase

A callback class for subtour elimination

_x

_n

_edges

callback()

_getModel()

A method to build COPT model

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

setObj(c)

A method to set the 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) – coefficients of new constraint
rhs (float) – right-hand side of new constraint

Returns:

new model with the added constraint

Return type:

optModel

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

Bases: tspABModel

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

_model

COPT model

Type:: COPT model

num_nodes

Number of nodes

Type:: int

edges

List of edge index

Type:: list

_getModel()

A method to build COPT model

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

setObj(c)

A method to set the 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) – coefficients 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.copt.tsp.tspMTZModelRel(num_nodes)

Bases: tspMTZModel

This class is relaxation of tspMTZModel.

_model

COPT model

Type:: COPT model

num_nodes

Number of nodes

Type:: int

edges

List of edge index

Type:: list

_getModel()

A method to build COPT 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

pyepo.model.copt.tsp.num_nodes = 5