pyepo.model.grb.tsp

Traveling salesman problem

Classes

tspABModel	Gurobi-backed TSP abstract base. Provides paired-variable setObj /
tspGGModel	Gavish-Graves (GG) formulation.
tspGGModelRel	LP relaxation of the GG formulation.
tspDFJModel	Danzig-Fulkerson-Johnson (DFJ) formulation with lazy subtour elimination.
tspMTZModel	Miller-Tucker-Zemlin (MTZ) formulation.
tspMTZModelRel	LP relaxation of the MTZ formulation.

Module Contents

class pyepo.model.grb.tsp.tspABModel(num_nodes: int, *args, **kwargs)

Bases: pyepo.model.bases.tspABBase, pyepo.model.grb.grbmodel.optGrbModel

Gurobi-backed TSP abstract base. Provides paired-variable setObj / solve / _addExtraConstr shared by GG and MTZ. DFJ overrides those.

setObj(c: numpy.ndarray | torch.Tensor | list) → None

A method to set the objective function

Parameters:

c – cost vector

solve() → tuple[numpy.ndarray, float]

A method to solve model

class pyepo.model.grb.tsp.tspGGModel(num_nodes: int, *args, **kwargs)

Bases: tspABModel

Gavish-Graves (GG) formulation.

relax() → tspGGModelRel

A method to get linear relaxation model

class pyepo.model.grb.tsp.tspGGModelRel(num_nodes: int, *args, **kwargs)

Bases: tspGGModel

LP relaxation of the GG formulation.

solve() → tuple[numpy.ndarray, float]

A method to solve model — returns fractional solution.

relax() → NoReturn

A forbidden method to relax MIP model

getTour(sol: numpy.ndarray | torch.Tensor | list) → list[int]

A forbidden method to get a tour from solution

class pyepo.model.grb.tsp.tspDFJModel(num_nodes: int, *args, **kwargs)

Bases: tspABModel

Danzig-Fulkerson-Johnson (DFJ) formulation with lazy subtour elimination.

Uses one undirected Var per edge (x[j,i] aliases x[i,j]), so the paired-vars setObj / solve / _addExtraConstr inherited from tspABModel are overridden here.

setObj(c: numpy.ndarray | torch.Tensor | list) → None

A method to set the objective function

Parameters:

c – cost vector

solve() → tuple[numpy.ndarray, float]

A method to solve model

class pyepo.model.grb.tsp.tspMTZModel(num_nodes: int, *args, **kwargs)

Bases: tspABModel

Miller-Tucker-Zemlin (MTZ) formulation.

relax() → tspMTZModelRel

A method to get linear relaxation model

class pyepo.model.grb.tsp.tspMTZModelRel(num_nodes: int, *args, **kwargs)

Bases: tspMTZModel

LP relaxation of the MTZ formulation.

solve() → tuple[numpy.ndarray, float]

A method to solve model — returns fractional solution.

relax() → NoReturn

A forbidden method to relax MIP model

getTour(sol: numpy.ndarray | torch.Tensor | list) → list[int]

A forbidden method to get a tour from solution