How to: Create and Solve a Nonlinear Model using a Third-party Solver
You can use nonlinear programming and Solver Foundation Services to create and solve nonlinear models using a third party solver. 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 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.
This table shows the following for each segment of the route: a segment identifier, the starting port, the distance, and boundaries for departure from 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 |
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. |
To register the third-party solver
-
Create a console application named ShippingRoutes.
-
Add a reference to Microsoft Solver Foundation on the .NET tab of the Add Reference dialog box.
-
Add a reference to the assembly for the third-party solver.
-
After you install the third-party solver, add a file called app.config to the Visual Studio solution.
The following XML shows the contents of an app.config file for a Solver Foundation project for a solver named the Fabrikam solver that specifies INonlinearSolver as the nonlinear programming interface.
Note
For detailed information about the attributes in this configuration file, see Developing with Solver Foundation Services (SFS).
<?xml version="1.0" encoding="utf-8" ?> <configSections> <section name="MsfConfig" type= "Microsoft.SolverFoundation.Services.MsfConfigSection, Microsoft.Solver.Foundation, Version=3.0.1.xxxx, Culture=neutral, PublicKeyToken=xxxxxxxxxx" allowLocation="true" allowDefinition="Everywhere" allowExeDefinition="MachineToApplication" restartOnExternalChanges="true" requirePermission="true" /> </configSections> <MsfConfig> <MsfPluginSolvers> <MsfPluginSolver name="fabrikam" capability="NLP" interface="INonlinearSolver" assembly="fabrikamPlugIn.dll" solverclass="SolverFoundation.Plugin.fabrikam.fabrikamSolver" directiveclass="SolverFoundation.Plugin.fabrikam.fabrikamDirective" parameterclass="SolverFoundation.Plugin.fabrikam.fabrikamParameter" /> </MsfPluginSolvers> </MsfConfig> </configuration>
To use nonlinear programming and Solver Foundation Services to minimize fuel consumption and emissions
-
Add the following Imports or using statements to the top of the program code file.
-
Create a class that defines route segment data. The class must include properties for the data shown 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
-
In the Main method, use the following code to populate a new Segment object with the route segment data from 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"} }
-
In the Main method, add the following code to get the context environment for a solver and to create a new model.
-
Add a set that represents route segments, a parameter that represents the distances of the route segments, and two parameters that represent the early and late departure times. In the following code, the early parameter represents the earliest time that a ship can depart from port. The late parameter represents the latest time that a ship can depart from port. The time values are in elapsed days.
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)
-
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)
-
Add a constraint that restricts the departure time based on the early and late values, a constraint that calculates the 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)
-
Add a goal to specify that the solver should minimize fuel consumption. The goal should include a cubic function to calculate fuel consumption. This function should also account for time spent waiting in port.
-
Use the following code to solve the model and write decision values to the solver internal database. Use a directive that is specific to the third-party solver. Each third-party solver provides a directive class that allows you to use solver-specific features, if necessary.
fabrikamDirective directive = new fabrikamDirective(); directive.someProperty = someValue; context.Solve(directive); context.PropagateDecisions();
-
Print out fuel consumption and segment data.
-
Press F5 to build and run the code.
Note
For an example that solves the shipping route model by using the internal hybrid local search solver, see How to: Use Nonlinear Programming using the Solver Foundation Services APIs