Hierarchical Optimization Tolerance Issue
AnsweredHi everyone,
I'm working on solving a simple multi-objective linear program with two minimization objectives. All variables are continuous, constraints and objectives are linear. Here's what I've done so far:
Pareto Front: To plot the Pareto front, I used a blended approach. Additionally, I manually implemented a hierarchical method by adding the necessary constraints and modifying the objectives. Both approaches worked well.
Built-in Functionality: I wanted to use the built-in ObjNPriority
functionality but ran into an issue—it doesn't seem to respect the specified tolerances. This is how I define the objectives in Python:
self.model.ModelSense = GRB.MINIMIZE
self.model.setObjectiveN(
gp.quicksum(
self.vars_pgrid2load[t] * self.time_delta / 1000 * self.tariff[t]
for t in range(self.n_steps)
),
index=0,
priority=1,
reltol=self.alpha,
)
self.model.setObjectiveN(
gp.quicksum(self.vars_max_load[i] for i in range(self.n_steps // 96)),
index=1,
priority=0,
)
To troubleshoot, I tried modifying the tolerance values in an exported LP file and solving it using the CLI. Unfortunately, this approach didn't resolve the problem either.
Objective Priorities: The first objective has priority 1, and the second objective has priority 0.
Default Behavior: With default settings for both absolute and relative tolerances, the value of the first objective for a sample instance is approximately 88.52.
RelTol: Changing the RelTol of the first objective to any value > 0 has no effect.
AbsTol: If I leave RelTol at its default value of 0 and set AbsTol to any value larger than 1e-4, the value of the first objective degrades to approx. 89.34, while the second objective improves to its optimal value.
What am I missing?
Thanks in advance for your help!
-
Hi Eike,
This is a bit of a tricky one. If you look at the docs for setObjectiveN you will see the abstol and reltol parameters refer to ObjNAbsTol and ObjNRelTol respectively. In the docs for ObjNAbsTol we find the following:
Objective degradations are handled differently for multi-objective LP models. For LP models, solution quality for higher-priority objectives is maintained by fixing some variables to their values in previous optimal solutions. These fixings are decided using variable reduced costs. The value of the
ObjNAbsTol
parameter indicates the amount by which a fixed variable’s reduced cost is allowed to violate dual feasibility. The value of the related ObjNRelTol attribute is ignored.So it is expected that the reltol parameter is ignored in setObjectiveN. I think we will make this more clear in the docs.
Note that if you add a dummy integer variable to your problem, then this will cause the solver to handle the problem like a MILP, and the reltol parameter can be used.
- Riley
1 -
Hi Riley,
Thanks for making this clear. For now, I am using a dummy integer (binary) variable. Surprisingly, this also significantly improves the runtime of my manually implemented hierarchical approach.
Cheers,
Eike0
Please sign in to leave a comment.
Comments
2 comments