patternMinor
Defining the goal function in an optimization problem
Viewed 0 times
problemthegoalfunctionoptimizationdefining
Problem
I have an optimization problem. There are a few quantities, call them $a, b, c$, that describe how good a solution is. However, they all have different priority, from highest to lowest: $a, b, c$.
The goal is to minimize the values of $a, b, c$. The difference in priorities means that the solution with identical value of $a$, lower value of $b$ is lower than the other solution, no matter what the value of $c$ is. Similarly, if the value of $a$ is lower, then no matter what $b$ or $c$ is, the solution is better better than the other solution.
What's the best way to define a goal function for this problem? I don't know the range of those values. I was thinking about using some weight parameters, like multiplying $a$ by the greatest weight, $b$ by lower weight, and $c$ by the lowest weight value.
The goal is to minimize the values of $a, b, c$. The difference in priorities means that the solution with identical value of $a$, lower value of $b$ is lower than the other solution, no matter what the value of $c$ is. Similarly, if the value of $a$ is lower, then no matter what $b$ or $c$ is, the solution is better better than the other solution.
What's the best way to define a goal function for this problem? I don't know the range of those values. I was thinking about using some weight parameters, like multiplying $a$ by the greatest weight, $b$ by lower weight, and $c$ by the lowest weight value.
Solution
If you know the minimum and maximum values for $a,b,c$, you can use a weighted linear combination. e.g., if $a,b,c \in [0,1000]$ (they are all between 0 and 1000), then you can use the objective function
$$\Phi(a,b,c) = 10^6 a + 10^3 b + c.$$
Minimizing this function is guaranteed to be optimal under your partial order.
Sometimes, even when you don't have upper and lower bounds, you can still use an objective function like the one above, as a heuristic. It's not guaranteed to give optimal results, but it might be good enough in your particular application.
$$\Phi(a,b,c) = 10^6 a + 10^3 b + c.$$
Minimizing this function is guaranteed to be optimal under your partial order.
Sometimes, even when you don't have upper and lower bounds, you can still use an objective function like the one above, as a heuristic. It's not guaranteed to give optimal results, but it might be good enough in your particular application.
Context
StackExchange Computer Science Q#57219, answer score: 3
Revisions (0)
No revisions yet.