Keep epsilons as variables throughout
In the current implementation of rtc-tools the epsilons computed in a certain priority are used to create constrains for the remaining part of the optimization problem. However, it will be more fair to keep the epsilons as variables throughout and introduce a constraint on the epsilons to impose pareto-optimality.
Let me give an example. Suppose priority one we have the constraint: x_t - \epsilon_t <= 0
for t \in \{1,2\}
, the objective function is \sum\limits_t \epsilon_t
and the optimal solution found is \epsilon_t^\ast = [0.1, 0]
. Then in the remaining part of the optimization problem rtc-tools uses the constraints: x_t - \epsilon_t^\ast <= 0
for t \in \{1,2\}
.
Suppose that at a later priority we want to minimize x_t^2
. A better solution would have been, for e.g., \epsilon_t^\prime = [0.05, 0.05]
(assuming that this is also feasible). However, since we are (arbitrarily) restricting the solution space we don't have any room left to optimize.
The alternative would be to keep the constraint: x_t - \epsilon_t <= 0
for t \in \{1,2\}
and add \epsilon_1 + \epsilon_2 <= 0.1
. So that x_t^\ast = [0.05, 0.05]
is a feasible solution.
Note that this implementation is different from the current one only when the epsilons are non-zero, that is when the targets are not met.
This will be a shift from the way goal programming is dealt with right now. I'll point out a couple of advantages and disadvantages that came up while discussing with Tjerk. First the advantages:
- fairness: what I propose seems to me a more fair way to set up the optimization. There is no arbitrary restrictions added to the solution space and therefore the final solution obtained is a more truly global optimal
- better results: in situations like the one in the example this approach leads to a better final solution
- infeasibilities: this may or may not turn out to be true, but should be kept in mind. We now have fairly simple problems where the step between epsilon variable to using the epsilon to create constraints leads to infeasibilities. (This problem arises with both continuous and mixed-integer quadratic programming using cplex. I'll investigate this further.) In any case, I think that if the epsilons are kept as variables these infeasibilities should disappear.
Disadvantages:
- significant restructuring of the goal programming and all that it entails. This may not be a complete disadvantage. In the current implementation, we need to check that the constraints we introduce are linearly independent with the previous ones. This check will be not be needed as linearly independence is guaranteed by construction.
- different results: this is a problem only on instances in which many target goals are not met.
- computational complexity: we will be increasing substantially the number of variables and this can have negative effects on the performances. I would guess that for linear programs (both continuous and mixed-integer) with commercial solvers this would not be a great problem as we are introducing almost disjoint set of constraints. However, this may be quite problematic for nonlinear programs. Especially if we have many targets on nonlinear functions.
@baayen, @vreeken, @jvande42b thoughts?