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.

    
    using Microsoft.SolverFoundation.Common;
    using 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 string StartingPort { get; set; }
    
        // A unique identifier for the segment.
        public int Id { get; set; }
    
        // Segment distance in nautical miles.
        public double Distance { get; set; }
    
        // The earliest time (in hours) when the ship can depart from port.
        public double MinDepartDay { get; set; }
    
        // The earliest time (in days) when the ship can depart from port.
        public double MinDepartTime { get { return MinDepartDay * 24.0; } }
    
        // The latest time (in hours) when the ship can depart from port.
        public double MaxDepartDay { get; set; }
    
        // The latest time (in days) when the ship can depart from port.
        public double MaxDepartTime { get { return MaxDepartDay * 24.0; } }
    
        // The departure time.
        public double DepartTime { get; set; }
    
        // The departure day.
        public double DepartDay { get { return DepartTime / 24.0; } }
    
        // The average sailing speed (in knots).
        public double Knots { get; set; }
    
        // Time in port.
        public double WaitTime { get; set; }
    
        // Number of days in port.
        public double WaitDays { get { return WaitTime / 24.0; } }
    
        // Returns a string representation of the Segment.
        public override string ToString()
        {
            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));
        }
    }
    
    
    
  5. In the Main method, use the following code to populate a new Segment object with the route segment data shown in the table.

    
      Segment[] segmentData = new Segment[] { 
      new Segment { Id = 0, Distance = 0, MinDepartDay = 0, MaxDepartDay = 0,
          StartingPort = "Vancouver" },
      new Segment { Id = 1, Distance = 510, MinDepartDay = 1, MaxDepartDay = 4,
          StartingPort = "Seattle" },
      new Segment { Id = 2, Distance = 2699, MinDepartDay = 50, MaxDepartDay = 65,
          StartingPort = "Busan" },
      new Segment { Id = 3, Distance = 838, MinDepartDay = 70, MaxDepartDay = 75,
          StartingPort = "Kaohsiung" },
      new Segment { 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.

    
    SolverContext context = SolverContext.GetContext();
    Model 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.

    
    Set segments = new Set(Domain.Integer, "segments");
    
    Parameter distance = new Parameter(Domain.RealNonnegative, "distance", segments);
    distance.SetBinding(segmentData, "Distance", "Id");
    
    Parameter early = new Parameter(Domain.RealNonnegative, "early", segments);
    early.SetBinding(segmentData, "MinDepartTime", "Id");
    
    Parameter late = new Parameter(Domain.RealNonnegative, "late", segments);
    late.SetBinding(segmentData, "MaxDepartTime", "Id");
    model.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.

    
    Decision speed = new Decision(Domain.RealRange(14, 20), "speed", segments);
    speed.SetBinding(segmentData, "Knots", "Id");
    
    Decision time = new Decision(Domain.RealRange(0, 100 * 24), "time", segments);
    time.SetBinding(segmentData, "DepartTime", "Id");
    
    Decision wait = new Decision(Domain.RealRange(0, 100 * 24), "wait", segments);
    wait.SetBinding(segmentData, "WaitTime", "Id");
    model.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.AddConstraint("bounds", Model.ForEach(segments, 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.AddConstraint("times", Model.ForEachWhere(segments,
      s => time[s - 1] + distance[s - 1] / speed[s - 1] + wait[s] == time[s],
      s => (s > 0)));
    
    model.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.

    
    Goal fuel = model.AddGoal("fuel", GoalKind.Minimize, Model.Sum(Model.ForEach(segments,
      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('-', segmentData[0].ToString().Length));
    foreach (var seg in segmentData)
    {
        Console.WriteLine(seg);
    }
    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