Skip to content
  • Tjerk Vreeken's avatar
    Add mixin to linearize goal order · 6d5cc07d
    Tjerk Vreeken authored
    For some problems it is preferred to not introduce any non-linear terms in
    the objective. For example, when using a MILP solver, one wants the entire
    problem to remain linear. This sometimes clashed with the desire for an
    order 2 goal, which steers the solution in the direction of many small
    exceedences instead of one large exceedence. An order 1 goal does not
    distuinguish between the two.
    
    This commit adds functionality to linearly approximate the goal order.
    That way, one can keep the problem fully linear, why getting some of the
    benefits of higher order goals back.
    
    By default, all goals will be linearized when inheriting from
    LinearizedOrderGPMixin. This behavior can also be overridden by setting
    `linearize_goal_order` to False in goal_programming_options(). The
    linearization can also be controlled on the level of a goal by making a
    goal inherit from LinearizedOrderGoal and setting `linearize_order` to
    either True or False.
    
    Typical use-cases for this fine-grained control are:
    - `linearize_goal_order` is True (default) to avoid a QP problem turning
      into a QCP problem when `keep_soft_constraints` is set. The last
      priority can however be solved as a QP problem (instead of LP), because
      this quadratic objective will _not_ turn into a constraint.
    - For performance reasons, one might want to linearize specific higher
      order goals, but keep others as-is.
    
    Aside from solvers which only handle LP and not QP, using a linearly
    approximated goal order is also useful when `keep_soft_constraints` is
    set. A quadratic problem in priority 1 would mean a quadratically
    _constrained_ problem in priority 2 with that option, something that can
    be much harder to solve.
    
    Note that higher order minimization goals do not work cannot be
    linearized. This is because a function range is lacking over which to
    linearize. Instead, users are requested to give these minimization goals
    e.g. a target_min = target_max = 0.0 (and a proper function range), such
    that they can be linearized. Minimization goals with order 1 are
    supported, as they do not have to be linearized.
    6d5cc07d