student's night out problem solved with lingo
The Student's Night out Problem will be solved with a rigid model and with a flexible model.
From-to chart with distances
The objective function of the Shortest Path Problem will be to minimize the distance traveled from the starting node to the overall destination. In the example above it will be to minimize the path between the engineering building and Springboks. This will be achieved by choosing a path between two nodes and indicating it with a "1"; if the path is not chosen it will be indicated with a "0". The 1 and 0 will be that path's coefficient. The objective function will minimize the sum of all the products of the coefficient and path distances.
Rigid model problem
The cells in green indicates the paths that could be taken from a specific node to the next node. The cells with the "M" in them indicates paths that do not exist. The transhipment problem ignores any paths that do not exist by not building the non-existing paths into the model. This makes for quick solving in optimazition software and more complicated and larger problems can be solved. The negative side of this techniques is that the model is a very rigid one.
For example suppose a new path is open and can now be part of the model. The model, based on the transhipment problem, will now have to be redesigned to allow for this extra path. This can be time consuming and not what you would want in a model.
LINGO was applied to the Student's Night Out Problem and the following input and output was given:
For example suppose a new path is open and can now be part of the model. The model, based on the transhipment problem, will now have to be redesigned to allow for this extra path. This can be time consuming and not what you would want in a model.
LINGO was applied to the Student's Night Out Problem and the following input and output was given:
input
output
Flexible model
The demo version of Lingo can only handle 30 integer variables and the example above has more than 30. To demonstrate LINGO the example above has been reduced to the following example.
The cells in green indicates the open paths from a node to a destination node. The cells containing the letter "M" are paths that do not exist in the problem statement at the moment. The "M" signifies a very large number (9999). The reason why we use a large number to indicate paths that do not exist between nodes is the next discussing point.
Recall that the objective function of the Shortest Path Problem will be to minimize the distance traveled from the starting node to the overall destination and the objective function will minimize the sum of all the products of the coefficient and path distances.
Paths that do not exist are indicated with a very large number. The objective function will automatically skip all the paths that distances are to large relative to the distances of the paths that do exist. The paths that do not exist will simple not be chosen as a solution.
Recall that the objective function of the Shortest Path Problem will be to minimize the distance traveled from the starting node to the overall destination and the objective function will minimize the sum of all the products of the coefficient and path distances.
Paths that do not exist are indicated with a very large number. The objective function will automatically skip all the paths that distances are to large relative to the distances of the paths that do exist. The paths that do not exist will simple not be chosen as a solution.
LINGO was applied to the Student's Night Out Problem and the following input and output was given: