Export (0) Print
Expand All

How to: Use Nonlinear Programming using the Solver Foundation Services APIs

Solver Foundation 3.0

You can use nonlinear programming to create and solve nonlinear models. This topic provides an example of a nonlinear model that minimizes fuel consumption on a shipping route. The objective is to minimize the fuel consumption and emissions on the shipping route by optimizing speed on each segment of the shipping route. This example is based on a problem described by K Fagerholt, G Laporte, and I Norstad in Journal of the Operational Research Society 61 (March, 2010), pages 523-529.

Note Note

Your computer might show different names or locations for some of the Visual Studio user interface elements in the following instructions. The Visual Studio edition that you have and the settings that you use determine these elements. For more information, see Visual Studio Settings.

This table shows the following for each segment: a segment identifier, the starting port, the distance, and time windows for arrival at port that specify the earliest and latest time that a ship may depart from port. The time values are in elapsed days.

Segment

Starting port

Distance

Early

Late

0

Vancouver

0

0

0

1

Seattle

510

1

4

2

Busan

2699

50

65

3

Kaohsiung

838

70

75

4

Hong Kong

3625

74

80

To use nonlinear programming to minimize fuel consumption and emissions

  1. Create a console application named ShippingRoutes.

  2. Add a reference to Microsoft Solver Foundation on the .NET tab of the Add Reference dialog box.

  3. Add the following Imports or using statements to the top of the program code file.

    
    Imports Microsoft.SolverFoundation.Common
    Imports Microsoft.SolverFoundation.Services
    
    
    
  4. Create a class that defines route segment data. The class must include properties for the data specified in the preceding table, and additional properties that represent sailing speed, in knots, time in port, and the number of days in port. The following code creates this class.

    
    Class Segment
    
        ' The name of the starting port.
        Public Property StartingPort() As String
            Get
                Return m_StartingPort
            End Get
            Set(ByVal value As String)
                m_StartingPort = value
            End Set
        End Property
        Private m_StartingPort As String
    
        ' A unique identifier for the segment.
        Public Property Id() As Integer
            Get
                Return m_Id
            End Get
            Set(ByVal value As Integer)
                m_Id = value
            End Set
        End Property
        Private m_Id As Integer
    
        ' Segment distance in nautical miles.
        Public Property Distance() As Double
            Get
                Return m_Distance
            End Get
            Set(ByVal value As Double)
                m_Distance = value
            End Set
        End Property
        Private m_Distance As Double
    
        ' The earliest time (in hours) when the ship may depart from port.
        Public Property MinDepartDay() As Double
            Get
                Return m_MinDepartDay
            End Get
            Set(ByVal value As Double)
                m_MinDepartDay = value
            End Set
        End Property
        Private m_MinDepartDay As Double
    
        ' The earliest time (in days) when the ship may depart from port.
        Public ReadOnly Property MinDepartTime() As Double
            Get
                Return MinDepartDay * 24.0
            End Get
        End Property
    
        ' The latest time (in hours) when the ship may depart from port.
        Public Property MaxDepartDay() As Double
            Get
                Return m_MaxDepartDay
            End Get
            Set(ByVal value As Double)
                m_MaxDepartDay = value
            End Set
        End Property
        Private m_MaxDepartDay As Double
    
        ' The latest time (in days) when the ship may depart from port.
        Public ReadOnly Property MaxDepartTime() As Double
            Get
                Return MaxDepartDay * 24.0
            End Get
        End Property
    
        ' The departure time.
        Public Property DepartTime() As Double
            Get
                Return m_DepartTime
            End Get
            Set(ByVal value As Double)
                m_DepartTime = value
            End Set
        End Property
        Private m_DepartTime As Double
    
        ' The departure day.
        Public ReadOnly Property DepartDay() As Double
            Get
                Return DepartTime / 24.0
            End Get
        End Property
    
        ' The average sailing speed (in knots).
        Public Property Knots() As Double
            Get
                Return m_Knots
            End Get
            Set(ByVal value As Double)
                m_Knots = value
            End Set
        End Property
        Private m_Knots As Double
    
        ' Time in port.
        Public Property WaitTime() As Double
            Get
                Return m_WaitTime
            End Get
            Set(ByVal value As Double)
                m_WaitTime = value
            End Set
        End Property
        Private m_WaitTime As Double
    
        ' Number of days in port.
        Public ReadOnly Property WaitDays() As Double
            Get
                Return WaitTime / 24.0
            End Get
        End Property
    
        ' Returns a string representation of the Segment.
        Public Overrides Function ToString() As String
            Return [String].Format("{0}   [{1}, {2}]   wait {5}   depart {3}   knots {4:f2}", _
                StartingPort.PadRight(15), MinDepartDay.ToString().PadLeft(2), _
                MaxDepartDay.ToString().PadLeft(2), DepartDay.ToString("f1").PadLeft(4), Knots, _
                WaitDays.ToString("f1").PadLeft(4))
        End Function
    End Class
    
    
    
  5. In the Main method, use the following code to populate a new Segment object with the route segment data shown in the table.

    
    Dim segmentData As Segment() = New Segment() {
        New Segment() With {.Id = 0, .Distance = 0, .MinDepartDay = 0, .MaxDepartDay = 0, _
            .StartingPort = "Vancouver"},
        New Segment() With {.Id = 1, .Distance = 510, .MinDepartDay = 1, .MaxDepartDay = 4, _
            .StartingPort = "Seattle"},
        New Segment() With {.Id = 2, .Distance = 2699, .MinDepartDay = 50, .MaxDepartDay = 65, _
            .StartingPort = "Busan"},
        New Segment() With {.Id = 3, .Distance = 838, .MinDepartDay = 70, .MaxDepartDay = 75, _
            .StartingPort = "Kaohsiung"},
        New Segment() With {.Id = 4, .Distance = 3625, .MinDepartDay = 74, .MaxDepartDay = 80, _
            .StartingPort = "Hong Kong"}
    }
    
    
    
  6. In the Main method, add the following code to get the context environment for a solver and to create a new model.

    
    Dim context As SolverContext = SolverContext.GetContext()
    Dim model__1 As Model = context.CreateModel()
    
    
    
  7. Add a set that represents route segments, parameters that represent the distances of the route segments, and two parameters that represent the boundaries for early and late departure times. In the following code, the early parameter represents the earliest time that a ship can depart from the port. The late parameter represents the latest time that a ship can depart from port.

    
    Dim segments As New [Set](Domain.[Integer], "segments")
    
    Dim distance As New Parameter(Domain.RealNonnegative, "distance", segments)
    distance.SetBinding(segmentData, "Distance", "Id")
    
    Dim early As New Parameter(Domain.RealNonnegative, "early", segments)
    early.SetBinding(segmentData, "MinDepartTime", "Id")
    
    Dim late As New Parameter(Domain.RealNonnegative, "late", segments)
    late.SetBinding(segmentData, "MaxDepartTime", "Id")
    model__1.AddParameters(distance, early, late)
    
    
    
  8. Add a decision that represents the speed in knots, a decision that represents the departure time, and add a decision that represents time spent waiting in port. Speed is the primary decision variable.

    
    Dim speed As New Decision(Domain.RealRange(14, 20), "speed", segments)
    speed.SetBinding(segmentData, "Knots", "Id")
    
    Dim time As New Decision(Domain.RealRange(0, 100 * 24), "time", segments)
    time.SetBinding(segmentData, "DepartTime", "Id")
    
    Dim wait As New Decision(Domain.RealRange(0, 100 * 24), "wait", segments)
    wait.SetBinding(segmentData, "WaitTime", "Id")
    model__1.AddDecisions(speed, time, wait)
    
    
    
  9. Add a constraint that restricts the departure time based on the early and late values, a constraint that calculates departure time for the current segment, and a constraint that sets the initial wait time value.

    
    model__1.AddConstraint("bounds", Model.ForEach(segments, Function(s) early(s) <= time(s) <= late(s)))
    
    ' The departure time for segment s is the sum of departure time for the previous segment,
    ' the sailing time, and time in port.
    model__1.AddConstraint("times", Model.ForEachWhere(segments, _
        Function(s) time(s - 1) + distance(s - 1) / speed(s - 1) + wait(s) = time(s), Function(s) (s > 0)))
    
    model__1.AddConstraint("wait_0", wait(0) = 0)
    
    
    
  10. Add a goal to specify that the solver should minimize fuel consumption. The following goal includes a cubic function to calculate fuel consumption, which also accounts for time spent waiting in port.

    
    Dim fuel As Goal = model__1.AddGoal("fuel", GoalKind.Minimize, Model.Sum( _
        Model.ForEach(segments, Function(s) distance(s) * (0.0036 * Model.Power( _
        speed(s), 2) - 0.1015 * speed(s) + 0.8848) + 0.01 * wait(s))))
    
    
    
  11. Use the following code to solve the model and write decision values to the solver internal database.

    
    context.Solve()
    context.PropagateDecisions()
    
    
    
  12. Print out fuel consumption and segment data.

    
    Console.WriteLine([String].Format("Fuel consumption: {0:f2}", fuel.ToDouble()))
    Console.WriteLine()
    Console.WriteLine("Schedule:")
    Console.WriteLine(New String("-"c, segmentData(0).ToString().Length))
    
    For Each seg As Object In segmentData
        Console.WriteLine(seg)
    Next
    Console.ReadLine()
    
    
    
  13. Press F5 to build and run the code.

    The command window shows the following results.

    Fuel consumption: 1314.26
    
    Schedule:
    ------------------------------------------------------------------
    Vancouver         [ 0,  0]   wait  0.0   depart  0.0   knots 14.48
    Seattle           [ 1,  4]   wait  3.1   depart  3.1   knots 14.09
    Busan             [50, 65]   wait 56.5   depart 61.1   knots 14.09
    Kaohsiung         [70, 75]   wait  2.4   depart 71.5   knots 14.09
    Hong Kong         [74, 80]   wait  0.0   depart 74.0   knots 14.10
    
Show:
© 2014 Microsoft