Skip to content

A Transportation Problem

  This tutorial is an upgrade of the Practical Example from the main page. In this case, we are going to re-implement the transportation problem presented in the GAMS Tutorial by Richard E. Rosenthal using PyORlin's workflow. The purpose of this example is to provide a quick but complete overview of PyORlib and its features in a more realistic scenario.

Problem Formulation

  The transportation problem we will address is a classic instance of linear programming's transportation problem, which has historically served as a testing ground for the development of optimization technology. This transportation problem involves determining the optimal flow of a product from multiple sources (plants) to destinations (markets) to minimize costs while satisfying demands.

\[ \begin{align} \text{Minimize:} \quad & \sum_{i=1}^{n} \sum_{j=1}^{m} c_{ij} x_{ij} \\ \\ \text{Subject to:} \quad & \sum_{j=1}^{m} x_{ij} \leq a_{i} \quad \forall_{i} \\ & \sum_{i=1}^{n} x_{ij} \geq b_{j} \quad \forall_{j} \\ & x_{ij} \geq 0 \quad \forall_{ij}, \thinspace integer \\ & i=1,...,n; \quad j=1,...,m \\ \end{align} \]

  Before diving into the implementation, let's take a moment to familiarize ourselves with the key components of the model. This brief exploration will provide a better understanding of how these components work together.

  • Indices:

     \(i=\) plants; \(\quad j=\) markets.

  • Parameters (Given Data):

     \(a_{i}=\) supply of commodity of plant \(i\) (in cases).

     \(b_{j}=\) demand for commodity at market \(j\) (cases).

     \(c_{ij}=\) cost per unit shipment between plan \(i\) and market \(j\) ($/case).

  • Decision Variables:

     \(x_{ij}=\) amount of commodity to ship from plant \(i\) to market \(j\) (cases).

  • Constraints:

     Observe supply limit at plant \(i\): \(\sum_{j=1}^{m} x_{ij} \leq a_{i} \quad \forall_{i}\)

     Satisfy demand at market \(j\): \(\sum_{i=1}^{n} x_{ij} \geq b_{j} \quad \forall_{j}\)

  The GAMS tutorial describes a scenario with two canning plants and three markets. It provides sample supply, demand and cost data. We will use this same data to define our model.

New York Chicago Topeka Supply
Seattle 2.5 1.7 1.8 350
San Diego 2.5 1.8 1.4 600
Demand 325 300 275
A Transportation Problem

Solution Using PyORlib

  To model and solve the problem in Python, we will utilize PyORlib and its integration with CPLEX. However, it's worth noting that you have the flexibility to choose from various supported optimization engine integrations mentioned in the Optional Dependencies section, or even use your own custom implementations.

  1. Required Imports and Dependencies: Before proceeding, make sure you have PyORlib installed, along with the CPLEX engine integration. Once everything is set up, let's import all the necessary components and start building our transportation model: 
    1
2
3
4
5
6
7
8
    from dataclasses import dataclass
from math import inf

from pyorlib import Model, Engine
from pyorlib.engines.cplex import CplexEngine  # Can be replaced with other integration options.
from pyorlib.enums import ValueType, ParameterType, OptimizationType  # These enums are used for specifying value types, parameter types, and optimization types in PyORlib.
from pyorlib.structures import DimensionDefinition, ParameterDefinition, TermDefinition, MultiValueParameter  # Classes that are used for organizing and defining the structure of the model.
from pyorlib.validators import DimensionField, ParameterField  # Classes that are used for validating the dimensions and parameters of the model.
  2. Model Definition: In order to keep our code organized, readable, and maintainable over time, we will structure variable, parameter, and dimension definitions (metadata) in a clean and extensible manner using PyORlib's definition module. 
     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
    class TransportModelDefinition:
    """Transportation Nomenclature Definitions"""

    @dataclass(frozen=True)
    class Dimensions:
        n = DimensionDefinition(name="n", display_name="Total plants")
        m = DimensionDefinition(name="m", display_name="Total markets")

    @dataclass(frozen=True)
    class Parameters:
        a_i = ParameterDefinition(
            set_name="a_i",
            name=lambda i: f"a_{i}",
            display_name="Supply of commodity of plant i (in cases)",
            parameter_types={ParameterType.FIXED},
            value_types={ValueType.INTEGER},
            min=0,
        )
        b_j = ParameterDefinition(
            set_name="b_j",
            name=lambda j: f"b_{j}",
            display_name="Demand for commodity at market j (cases)",
            parameter_types={ParameterType.FIXED},
            value_types={ValueType.INTEGER},
            min=0,
        )
        c_i_j = ParameterDefinition(
            set_name="c_i_j",
            name=lambda i, j: f"c_{i}_{j}",
            display_name="Cost per unit shipment between plan i and market j ($/case)",
            parameter_types={ParameterType.FIXED},
            value_types={ValueType.CONTINUOUS},
            min=0,
        )

    @dataclass(frozen=True)
    class DecisionVariables:
        x_i_j = TermDefinition(
            set_name="x_i_j",
            name=lambda i, j: f"x_{i}_{j}",
            display_name="Amount of commodity to ship from plant i to market j (cases)",
        )
  3. Data Schema and Validations: Now that we have defined the model components, we can focus on handling data entry and validations for parameters and dimensions. For this task, we will use PyORlib's structures and validators. 
     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
    @dataclass
class TransportModelSchema:
    """Data Entry Validations"""

    n: int = DimensionField(min=TransportModelDefinition.Dimensions.n.min)
    m: int = DimensionField(min=TransportModelDefinition.Dimensions.m.min)

    a_i: MultiValueParameter = ParameterField(
        parameter_types=TransportModelDefinition.Parameters.a_i.parameter_types,
        value_types=TransportModelDefinition.Parameters.a_i.value_types,
        min=TransportModelDefinition.Parameters.a_i.min,
    )
    b_j: MultiValueParameter = ParameterField(
        parameter_types=TransportModelDefinition.Parameters.b_j.parameter_types,
        value_types=TransportModelDefinition.Parameters.b_j.value_types,
        min=TransportModelDefinition.Parameters.b_j.min,
    )
    c_i_j: MultiValueParameter = ParameterField(
        parameter_types=TransportModelDefinition.Parameters.c_i_j.parameter_types,
        value_types=TransportModelDefinition.Parameters.c_i_j.value_types,
        min=TransportModelDefinition.Parameters.c_i_j.min,
    )

    def __post_init__(self):
        if len(self.a_i.values) != self.n:
            raise ValueError(f"'a_i' values must have a length of {self.n}")
        if len(self.b_j.values) != self.m:
            raise ValueError(f"'b_j' values must have a length of {self.m}")
        if len(self.c_i_j.values) != self.n * self.m:
            raise ValueError(f"'c_i_j' values must have a length of {self.n * self.m}")
  4. Transportation Model: With the data entry schema in place, we can now define the transportation model. 
     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
    class TransportModel(Model):

    def __init__(self, engine: Engine, data: TransportModelSchema, debug: bool = False):
        super().__init__(engine=engine, name="Transportation Model", debug=debug)

        if data is None:
            raise ValueError("'data' parameter cannot be None.")

        # Dimensions
        n = self.add_dimension(name=TransportModelDefinition.Dimensions.n.name, value=data.n)
        m = self.add_dimension(name=TransportModelDefinition.Dimensions.m.name, value=data.m)

        n_range = range(1, n + 1)
        m_range = range(1, m + 1)

        # Parameters
        for i in n_range:  # Plant's supply values
            self.add_constant_to_set(
                set_name=TransportModelDefinition.Parameters.a_i.set_name,
                set_index=(i,),
                const_name=TransportModelDefinition.Parameters.a_i.name(i),
                value_type=data.a_i.value_type,
                value=data.a_i.values[i - 1],
            )
        a_i = self.get_term_set_by_name(name=TransportModelDefinition.Parameters.a_i.set_name)

        for j in m_range:  # Market's demands
            self.add_constant_to_set(
                set_name=TransportModelDefinition.Parameters.b_j.set_name,
                set_index=(j,),
                const_name=TransportModelDefinition.Parameters.b_j.name(j),
                value_type=data.b_j.value_type,
                value=data.b_j.values[j - 1],
            )
        b_j = self.get_term_set_by_name(name=TransportModelDefinition.Parameters.b_j.set_name)

        for i in n_range:
            for j in m_range:  # Costs
                self.add_constant_to_set(
                    set_name=TransportModelDefinition.Parameters.c_i_j.set_name,
                    set_index=(i, j),
                    const_name=TransportModelDefinition.Parameters.c_i_j.name(i, j),
                    value_type=data.c_i_j.value_type,
                    value=data.c_i_j.values[(i - 1) * m + (j - 1)],
                )
        c_i_j = self.get_term_set_by_name(name=TransportModelDefinition.Parameters.c_i_j.set_name)

        # Decision variables
        for i in n_range:
            for j in m_range:
                self.add_variable_to_set(
                    set_name=TransportModelDefinition.DecisionVariables.x_i_j.set_name,
                    set_index=(i, j),
                    var_name=TransportModelDefinition.DecisionVariables.x_i_j.name(i, j),
                    value_type=ValueType.INTEGER,
                    lower_bound=0,
                    upper_bound=inf,
                )
        x_i_j = self.get_term_set_by_name(name=TransportModelDefinition.DecisionVariables.x_i_j.set_name)


        # Supply limit at plants constraints
        for i in n_range:
            self.add_constraint(
                expression=sum(
                    x_i_j[i, j]
                    for j in m_range
                ) <= a_i[(i,)]
            )

        # Satisfy demand at markets constraints
        for j in m_range:
            self.add_constraint(
                expression=sum(
                    x_i_j[i, j]
                    for i in n_range
                ) >= b_j[(j,)]
            )

        # Objective function
        self.set_objective(
            opt_type=OptimizationType.MINIMIZE,
            expression=sum(
                c_i_j[i, j] * x_i_j[i, j]
                for i in n_range
                for j in m_range
            )
        )
  5. Model Optimization: Finally, having defined the transportation model class, we can create a new instance of it with our data and optimize it. 
     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
    # Instantiate the transportation model
model = TransportModel(
    engine=CplexEngine(),
    data=TransportModelSchema(
        n=2,
        m=3,
        a_i=MultiValueParameter(
            parameter_type=ParameterType.FIXED,
            value_type=ValueType.INTEGER,
            values=(350, 600),
        ),
        b_j=MultiValueParameter(
            parameter_type=ParameterType.FIXED,
            value_type=ValueType.INTEGER,
            values=(325, 300, 275),
        ),
        c_i_j=MultiValueParameter(
            parameter_type=ParameterType.FIXED,
            value_type=ValueType.CONTINUOUS,
            values=(2.5, 1.7, 1.8, 2.5, 1.8, 1.4),
        ),
    )
)

# Optimize the model
model.solve()

# Display solution
model.print_solution()
    Click here to view the complete code... 
      1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
    from dataclasses import dataclass
from math import inf

from pyorlib import Model, Engine
from pyorlib.engines.cplex import CplexEngine  # Can be replaced with other integration options.
from pyorlib.enums import ValueType, ParameterType, OptimizationType  # These enums are used for specifying value types, parameter types, and optimization types in PyORlib.
from pyorlib.structures import DimensionDefinition, ParameterDefinition, TermDefinition, MultiValueParameter  # Classes that are used for organizing and defining the structure of the model.
from pyorlib.validators import DimensionField, ParameterField  # Classes that are used for validating the dimensions and parameters of the model.


class TransportModelDefinition:
    """Transportation Nomenclature Definitions"""

    @dataclass(frozen=True)
    class Dimensions:
        n = DimensionDefinition(name="n", display_name="Total plants")
        m = DimensionDefinition(name="m", display_name="Total markets")

    @dataclass(frozen=True)
    class Parameters:
        a_i = ParameterDefinition(
            set_name="a_i",
            name=lambda i: f"a_{i}",
            display_name="Supply of commodity of plant i (in cases)",
            parameter_types={ParameterType.FIXED},
            value_types={ValueType.INTEGER},
            min=0,
        )
        b_j = ParameterDefinition(
            set_name="b_j",
            name=lambda j: f"b_{j}",
            display_name="Demand for commodity at market j (cases)",
            parameter_types={ParameterType.FIXED},
            value_types={ValueType.INTEGER},
            min=0,
        )
        c_i_j = ParameterDefinition(
            set_name="c_i_j",
            name=lambda i, j: f"c_{i}_{j}",
            display_name="Cost per unit shipment between plan i and market j ($/case)",
            parameter_types={ParameterType.FIXED},
            value_types={ValueType.CONTINUOUS},
            min=0,
        )

    @dataclass(frozen=True)
    class DecisionVariables:
        x_i_j = TermDefinition(
            set_name="x_i_j",
            name=lambda i, j: f"x_{i}_{j}",
            display_name="Amount of commodity to ship from plant i to market j (cases)",
        )


@dataclass
class TransportModelSchema:
    """Data Entry Validations"""

    n: int = DimensionField(min=TransportModelDefinition.Dimensions.n.min)
    m: int = DimensionField(min=TransportModelDefinition.Dimensions.m.min)

    a_i: MultiValueParameter = ParameterField(
        parameter_types=TransportModelDefinition.Parameters.a_i.parameter_types,
        value_types=TransportModelDefinition.Parameters.a_i.value_types,
        min=TransportModelDefinition.Parameters.a_i.min,
    )
    b_j: MultiValueParameter = ParameterField(
        parameter_types=TransportModelDefinition.Parameters.b_j.parameter_types,
        value_types=TransportModelDefinition.Parameters.b_j.value_types,
        min=TransportModelDefinition.Parameters.b_j.min,
    )
    c_i_j: MultiValueParameter = ParameterField(
        parameter_types=TransportModelDefinition.Parameters.c_i_j.parameter_types,
        value_types=TransportModelDefinition.Parameters.c_i_j.value_types,
        min=TransportModelDefinition.Parameters.c_i_j.min,
    )

    def __post_init__(self):
        if len(self.a_i.values) != self.n:
            raise ValueError(f"'a_i' values must have a length of {self.n}")
        if len(self.b_j.values) != self.m:
            raise ValueError(f"'b_j' values must have a length of {self.m}")
        if len(self.c_i_j.values) != self.n * self.m:
            raise ValueError(f"'c_i_j' values must have a length of {self.n * self.m}")


class TransportModel(Model):

    def __init__(self, engine: Engine, data: TransportModelSchema, debug: bool = False):
        super().__init__(engine=engine, name="Transportation Model", debug=debug)

        if data is None:
            raise ValueError("'data' parameter cannot be None.")

        # Dimensions
        n = self.add_dimension(name=TransportModelDefinition.Dimensions.n.name, value=data.n)
        m = self.add_dimension(name=TransportModelDefinition.Dimensions.m.name, value=data.m)

        n_range = range(1, n + 1)
        m_range = range(1, m + 1)

        # Parameters
        for i in n_range:  # Plant's supply values
            self.add_constant_to_set(
                set_name=TransportModelDefinition.Parameters.a_i.set_name,
                set_index=(i,),
                const_name=TransportModelDefinition.Parameters.a_i.name(i),
                value_type=data.a_i.value_type,
                value=data.a_i.values[i - 1],
            )
        a_i = self.get_term_set_by_name(name=TransportModelDefinition.Parameters.a_i.set_name)

        for j in m_range:  # Market's demands
            self.add_constant_to_set(
                set_name=TransportModelDefinition.Parameters.b_j.set_name,
                set_index=(j,),
                const_name=TransportModelDefinition.Parameters.b_j.name(j),
                value_type=data.b_j.value_type,
                value=data.b_j.values[j - 1],
            )
        b_j = self.get_term_set_by_name(name=TransportModelDefinition.Parameters.b_j.set_name)

        for i in n_range:
            for j in m_range:  # Costs
                self.add_constant_to_set(
                    set_name=TransportModelDefinition.Parameters.c_i_j.set_name,
                    set_index=(i, j),
                    const_name=TransportModelDefinition.Parameters.c_i_j.name(i, j),
                    value_type=data.c_i_j.value_type,
                    value=data.c_i_j.values[(i - 1) * m + (j - 1)],
                )
        c_i_j = self.get_term_set_by_name(name=TransportModelDefinition.Parameters.c_i_j.set_name)

        # Decision variables
        for i in n_range:
            for j in m_range:
                self.add_variable_to_set(
                    set_name=TransportModelDefinition.DecisionVariables.x_i_j.set_name,
                    set_index=(i, j),
                    var_name=TransportModelDefinition.DecisionVariables.x_i_j.name(i, j),
                    value_type=ValueType.INTEGER,
                    lower_bound=0,
                    upper_bound=inf,
                )
        x_i_j = self.get_term_set_by_name(name=TransportModelDefinition.DecisionVariables.x_i_j.set_name)


        # Supply limit at plants constraints
        for i in n_range:
            self.add_constraint(
                expression=sum(
                    x_i_j[i, j]
                    for j in m_range
                ) <= a_i[(i,)]
            )

        # Satisfy demand at markets constraints
        for j in m_range:
            self.add_constraint(
                expression=sum(
                    x_i_j[i, j]
                    for i in n_range
                ) >= b_j[(j,)]
            )

        # Objective function
        self.set_objective(
            opt_type=OptimizationType.MINIMIZE,
            expression=sum(
                c_i_j[i, j] * x_i_j[i, j]
                for i in n_range
                for j in m_range
            )
        )


# Instantiate the transportation model
model = TransportModel(
    engine=CplexEngine(),
    data=TransportModelSchema(
        n=2,
        m=3,
        a_i=MultiValueParameter(
            parameter_type=ParameterType.FIXED,
            value_type=ValueType.INTEGER,
            values=(350, 600),
        ),
        b_j=MultiValueParameter(
            parameter_type=ParameterType.FIXED,
            value_type=ValueType.INTEGER,
            values=(325, 300, 275),
        ),
        c_i_j=MultiValueParameter(
            parameter_type=ParameterType.FIXED,
            value_type=ValueType.CONTINUOUS,
            values=(2.5, 1.7, 1.8, 2.5, 1.8, 1.4),
        ),
    )
)

# Optimize the model
model.solve()

# Display solution
model.print_solution()

      Once you have implemented and solved the model using PyORlib, you will find the solution outputs displayed in the console logs as follows: 

    ------ MODEL SOLUTION ------

Objective function:
        Status: OPTIMAL
        Value:  1707.5
Terms:
        Name: x_1_1 | Type: Variable | Value type: Integer | lb: 0 | ub: inf | val: 50  
        Name: x_1_2 | Type: Variable | Value type: Integer | lb: 0 | ub: inf | val: 300  
        Name: x_2_1 | Type: Variable | Value type: Integer | lb: 0 | ub: inf | val: 275  
        Name: x_2_3 | Type: Variable | Value type: Integer | lb: 0 | ub: inf | val: 275

Recap

  In this tutorial, we explored how to use the PyORlib library to optimize a transportation problem—an upgrade from the practical example covered earlier. Throughout our journey, we gained hands-on experience applying PyORlib's powerful features to model and solve a real-world optimization challenge of transporting products between multiple sources and destinations.

  Firstly, we introduced the transportation problem and defined the sources, destinations, costs and demands. By structuring our model with PyORlib's definition module classes, we created an organized and readable representation of the transportation model. We also handled data entries and ensured valid input using PyORlib's data structures and validators.

  With our transportation model built, we then optimized it using PyORlib's techniques to find the lowest-cost flows that meet all demands. The console outputs displayed the solution, providing valuable insights. Overall, PyORlib proved to be a flexible and effective tool for tackling this classic optimization problem.

  In summary, this tutorial equipped us with the skills to leverage PyORlib's full capabilities for a variety of optimization challenges. Armed with our newfound knowledge of modeling, data processing, and optimization, we can now unlock the potential for impactful Python projects across many domains.