Hierarchical and Weighted Optimization
The OPTANO Modeling Framework emulates the multi-objective optimization of the Gurobi 7.x Solver. The following article explains the ideas behind the different options and an example illustrates the usage of multi-objective optimization within the OPTANO Modeling Framework.
Hierarchical Optimization
In the constructor of an Objective, you can assign a priority level to the objective. When you add several objectives to a model, the PriorityLevel is used to order the objectives during the solution process. A higher priority means that the objective will be optimized earlier, i.e. it has more impact on the final result of the optimization.
The hierarchical solution process works in the following way:
- Order the objectives descending by PriorityLevel
- For each objective obj:
- Solve the model, using obj as current objective
- Create a quality constraint that ensures that later solutions for other Objective s will not decrease the quality of obj.
- E.g. obj.Expression <= obj.CurrentValue (for a minimization objective)
- After all hierarchy levels have been treated, the quality constraints are dropped, so that the original model is restored.
- If the SolverConfiguration.ModelOutputFile is set, the model is written after each PriorityLevel was solved, but previous output files will be overwritten. However, the output files between two priority levels only differ by the quality conservation constraint, that is added after the respective priority level was solved.
- The "new" constraints will be written to the end of the output file and the constraint name is constructed as follows:
"multiObjectiveQuality_PrioLevel_"
+ previous PrioLevel +_Group_
+ "Name of the merged Objective for the previous PrioLevel"- Where the "Name of the merged Objective" consists of the concatenated (user-)names of all objectives that have the previous PrioLevel.
- Return a @OPTANO.Modeling.Optimization.Solver.Solution that contains the objective value for each PriorityLevel, as well as the objective value for each distinct objective (i.e. regardless of the objective's PriorityLevel).
- The Solution contains a Dictionary that stores the (merged) Objective.Name, using the respective PrioLevel as key.
- Since the merging of objectives of the same PrioLevel happens automatically, the user does not know the name. With the help of Solution.GetNameForMergedObjective, the Name that serves as key for Solution.GetObjectiveValue can be retrieved.
- Remark: This works for both, merged- and non-merged objectives.
- You do not need to "find out" the automatically created/extended unique name that was created for your objective (ref. ShortNames). The Solution.GetObjectiveValue will retrieve the objective, given either the Objective.Name or the "original name" that was assigned by the user. This works regardless of the current ModelScope.NameHandling.
Weighted Optimization
If several objectives have the same PriorityLevel, they are merged, using the Weight. The resulting objective will be the weighted average of all Objective s on a given PriorityLevel. I.e.:
// mergedObjective = \sum_{obj \in SamePriorityObjectives} \{ obj.Weight * obj.Expression \} / \sum_{obj \in SamePriorityObjectives} \{ obj.Weight \}
Combination of Hierarchical and Weighted Optimization
If there are objectives with different PriorityLevel and at the same time at least one priority level that contains more than one objective, the optimization will first merge the objectives as stated in the previous section and then treat the merged objectives according to the method that was shown in the Hierarchical Optimization section.
C# Example
This example illustrates the usage of different multi-objective optimization methods.
public static class OptanoExample
{
/// <summary>
/// An example to demonstrate the usage of multiple objectives.
/// </summary>
public static void BakeryModelMultiObjective()
{
var config = new Configuration()
{
NameHandling = NameHandlingStyle.UniqueLongNames,
};
using (var scope = new ModelScope(config))
{
// We want to decide which cakes to bake, given our current stock and considering multiple objectives.
var model = new Model { Name = "MyLittleBakery" };
// Our bakery can produce two different pies: Haslenut and Lemon Pie.
var recipes = new[]
{
new PieRecipe()
{
PieName = "Haslenut Pie",
Flour = 0.35,
Sugar = 0.2,
Milk = 0.25,
Haslenuts = 0.2,
LemonMixture = 0,
Revenue = 6
},
new PieRecipe()
{
PieName = "Lemon Pie",
Flour = 0.35,
Sugar = 0.3,
Milk = 0.15,
Haslenuts = 0,
LemonMixture = 0.15,
Revenue = 6
}
};
// Our current stock looks like this.
var stock = new BakeryStock()
{
AvailableFlour = 30,
AvailableSugar = 50,
AvailableMilk = 100,
AvailableHaslenuts = 10,
AvailableLemonMixture = 10
};
// Decision Variables: How many pies of which recipe should be produced.
var pieVariables = new VariableCollection<PieRecipe>(
model,
recipes,
"Pies",
(pie) => pie.PieName,
variableTypeGenerator: (pie) => VariableType.Integer);
// Make sure that we do not exceed our stock
model.AddConstraint(
Expression.Sum(recipes.Select(pie => pieVariables[pie] * pie.Flour))
<= stock.AvailableFlour,
"FlourStock");
model.AddConstraint(
Expression.Sum(recipes.Select(pie => pieVariables[pie] * pie.Sugar))
<= stock.AvailableSugar,
"SugarStock");
model.AddConstraint(
Expression.Sum(recipes.Select(pie => pieVariables[pie] * pie.Milk))
<= stock.AvailableMilk,
"MilkStock");
model.AddConstraint(
Expression.Sum(recipes.Select(pie => pieVariables[pie] * pie.Haslenuts))
<= stock.AvailableHaslenuts,
"HaslenutsStock");
model.AddConstraint(
Expression.Sum(recipes.Select(pie => pieVariables[pie] * pie.LemonMixture))
<= stock.AvailableLemonMixture,
"LemonMixtureStock");
// Maximize profit
// This has a higher priority than the minimization of the used sugar
var objRevenue = new Objective(
Expression.Sum(recipes.Select(pie => pieVariables[pie] * pie.Revenue)),
"Revenue",
ObjectiveSense.Maximize,
priorityLevel: 1);
// Add objective to the model
model.AddObjective(objRevenue);
// Solve the model
Solution bakerySolution;
using (var solver = new GLPKSolver())
{
bakerySolution = solver.Solve(model);
// Evaluate objective
var totalRevenue = objRevenue.Expression.Evaluate(bakerySolution.VariableValues);
// Or use value stored in the solution:
var solutionRevenue = bakerySolution.ObjectiveValues[objRevenue.Name];
Debug.Assert(totalRevenue.IsAlmost(solutionRevenue), "Both objective values should be the same with respect to ModelScope.EPSILON.");
// Print the solution.
var hasleNutPies = pieVariables[recipes[0]];
var lemonPies = pieVariables[recipes[1]];
var usedSugar = recipes.Sum(pie => pieVariables[pie].Value * pie.Sugar);
Console.WriteLine("\r\n\r\nFound the following Solution: ");
Console.WriteLine(string.Format("Revenue: {0}\r\nHaslenut Pies: {1}\r\nLemon Pies: {2}\r\nUsed Sugar: {3}\r\n\r\n", solutionRevenue, hasleNutPies.Value, lemonPies.Value, usedSugar));
// Update the model: Reduce the amount of used sugar as secondary objective
// Just make sure that the priority level is less than the revenue objective's priority level. E.g., -10 would work as well.
var objSugar = new Objective(
Expression.Sum(recipes.Select(pie => pieVariables[pie] * pie.Sugar)),
"Sugar",
ObjectiveSense.Minimize,
priorityLevel: 0);
model.AddObjective(objSugar);
// Resolve the updated model
bakerySolution = solver.Solve(model);
// Print the new Solution
solutionRevenue = bakerySolution.ObjectiveValues[objRevenue.Name];
usedSugar = recipes.Sum(pie => pieVariables[pie].Value * pie.Sugar);
Console.WriteLine("\r\n\r\nAfter reducing the used sugar, the solver found the following Solution: ");
Console.WriteLine(string.Format("Revenue: {0}\r\nHaslenut Pies: {1}\r\nLemon Pies: {2}\r\nUsed Sugar: {3}\r\n\r\n", solutionRevenue, hasleNutPies.Value, lemonPies.Value, usedSugar));
// Let's say we are even more interested in the health of our customers
// So we decide to even "trade" revenue for less sugar consumption
// Both objectives are given the same priority level
// Keep the weights at 1. Since the sugar objective will only be of magnitude 10e1 and the revenue objective will be in the dimension of 10e2, we already have an implicit weight of approximately 10 towards the revenue.
// The effective objective will simply be (objSugar + objRevenue)/(objSugar.Weight + objRevenue.Weight)
objSugar.PriorityLevel = 1;
// Resolve the updated model
bakerySolution = solver.Solve(model);
// Print the new Solution
// Note that the solution does not change. This is simply due to the fact that the increase of revenue for both pies is larger than the additional sugar that is required.
solutionRevenue = bakerySolution.ObjectiveValues[objRevenue.Name];
usedSugar = recipes.Sum(pie => pieVariables[pie].Value * pie.Sugar);
Console.WriteLine("\r\n\r\nFor the merged objective, the solver found the following Solution: ");
Console.WriteLine(string.Format("Revenue: {0}\r\nHaslenut Pies: {1}\r\nLemon Pies: {2}\r\nUsed Sugar: {3}\r\n\r\n", solutionRevenue, hasleNutPies.Value, lemonPies.Value, usedSugar));
}
Console.ReadLine();
}
}
}
/// <summary>
/// Business object in the <see cref="Program.BakeryModelMultiObjective"/>.
/// </summary>
public class PieRecipe
{
/// <summary>
/// Gets or sets the pie name.
/// </summary>
public string PieName { get; set; }
/// <summary>
/// Gets or sets the required flour.
/// </summary>
public double Flour { get; set; }
/// <summary>
/// Gets or sets the required sugar.
/// </summary>
public double Sugar { get; set; }
/// <summary>
/// Gets or sets the required milk.
/// </summary>
public double Milk { get; set; }
/// <summary>
/// Gets or sets the required haslenuts.
/// </summary>
public double Haslenuts { get; set; }
/// <summary>
/// Gets or sets the required lemon mixture.
/// </summary>
public double LemonMixture { get; set; }
/// <summary>
/// Gets or sets the revenue.
/// </summary>
public double Revenue { get; set; }
}
/// <summary>
/// Wrapper object in the <see cref="Program.BakeryModelMultiObjective"/>.
/// </summary>
public class BakeryStock
{
/// <summary>
/// Gets or sets the available flour.
/// </summary>
public double AvailableFlour { get; set; }
/// <summary>
/// Gets or sets the available sugar.
/// </summary>
public double AvailableSugar { get; set; }
/// <summary>
/// Gets or sets the available milk.
/// </summary>
public double AvailableMilk { get; set; }
/// <summary>
/// Gets or sets the available haslenuts.
/// </summary>
public double AvailableHaslenuts { get; set; }
/// <summary>
/// Gets or sets the available lemon mixture.
/// </summary>
public double AvailableLemonMixture { get; set; }
}