Module com.darkcollective.relix.processor
Package com.darkcollective.relix.processor.eval

Class SubsetOptimizer

java.lang.Object
com.darkcollective.relix.processor.eval.SubsetOptimizer
public final class SubsetOptimizer extends Object
Chooses the optimal subset of a group's rows under a linear objective and linear constraints — the 0/1 knapsack / portfolio-selection problem behind the OPTIMIZE operator.

Each candidate row gets a binary decision variable (in or out). The objective is SUM(objective) over the chosen rows; each constraint is SUM(expr) ≤|≥|= bound. Coefficients are obtained by evaluating the objective / constraint expressions against each row with the supplied OperandEvaluator. A row whose objective or any constraint coefficient is NULL is dropped from candidacy (it can never be chosen).

This class turns rows into a LinearProgram and reads the answer back; an installed solver performs the search. Everything relational stays on this side of that line — which rows are candidates, what a NULL coefficient means, how a constraint operator maps onto a bound — so two solvers cannot disagree about what OPTIMIZE means, only about how fast they answer.

choose(com.darkcollective.relix.ast.ObjectiveSense, com.darkcollective.relix.ast.Operand, java.util.List<com.darkcollective.relix.ast.OptimizeConstraint>, java.util.List<com.darkcollective.relix.processor.Row>, java.lang.String) returns the chosen rows for a feasible group (possibly empty — e.g. minimising a positive objective), or Optional.empty() when the group is proved infeasible (no assignment satisfies the constraints), so the caller can skip it. A solver that stops without deciding is the third case and raises an EvaluationException: nothing has been established about the group, so skipping it would report an answer no one worked out.

Instances are stateless apart from the immutable evaluator and solver references and are therefore thread-safe.

  • Constructor Details

    • SubsetOptimizer

      public SubsetOptimizer(OperandEvaluator evaluator)
      Constructs an optimizer that evaluates coefficients with the given evaluator and solves with the installed solver.
      Parameters:
      evaluator - the evaluator for per-row coefficient expressions; must not be null
      Throws:
      EvaluationException - if no solver is installed

    • SubsetOptimizer

      public SubsetOptimizer(OperandEvaluator evaluator, MathProgrammingSolver solver)
      Constructs an optimizer over an explicit solver.
      Parameters:
      evaluator - the evaluator for per-row coefficient expressions; must not be null
      solver - the solver to search with; must not be null

  • Method Details

    • choose

      public Optional<List<Row>> choose(ObjectiveSense sense, Operand objective, List<OptimizeConstraint> constraints, List<Row> groupRows, String groupLabel)
      Solves the subset-selection problem for one group.
      Parameters:
      sense - maximise or minimise the objective; must not be null
      objective - the per-row objective coefficient expression; must not be null
      constraints - the linear constraints; must not be null
      groupRows - the candidate rows of the group; must not be null
      groupLabel - how to name this group in a diagnostic; must not be null
      Returns:
      the chosen rows for a feasible group (possibly empty), or Optional.empty() if the group is infeasible
      Throws:
      EvaluationException - if a coefficient evaluates to a non-numeric value, or the solver did not decide the group

    • allocate

      public Optional<List<AllocationRow>> allocate(ObjectiveSense sense, Operand objective, List<OptimizeConstraint> constraints, double lo, double hi, List<Row> groupRows, String groupLabel)
      Solves the continuous-allocation (LP) problem for one group.

      Each candidate row receives a continuous decision variable in [lo, hi]. All rows are returned (no row is discarded), each paired with its solver-assigned allocation value. An infeasible group returns Optional.empty().

      Parameters:
      sense - maximise or minimise the objective; must not be null
      objective - the per-row coefficient expression; must not be null
      constraints - the linear constraints; must not be null
      lo - the lower bound for each row's allocation variable
      hi - the upper bound for each row's allocation variable
      groupRows - the candidate rows of the group; must not be null
      groupLabel - how to name this group in a diagnostic; must not be null
      Returns:
      every row paired with its allocation for a feasible group, or Optional.empty() if the group is infeasible
      Throws:
      EvaluationException - if a coefficient evaluates to a non-numeric value, or the solver did not decide the group

    • setcover

      public Optional<List<Row>> setcover(List<Row> candidates, List<List<Integer>> coveringSets)
      Solves the exact minimum covering problem for one candidate set.

      This is the MIP set-cover formulation: given a list of candidate rows and a list of demanded t-tuple covering sets (each a list of candidate indices that cover that t-tuple), finds the minimum-cardinality subset of candidates that covers every demanded t-tuple.

      One binary variable per candidate (weight 1 — we minimise count); one ≥ 1 constraint per demanded t-tuple (at least one covering candidate must be chosen). A demanded t-tuple with no covering candidates makes the problem infeasible.

      Parameters:
      candidates - the candidate rows (may be empty — returns empty list)
      coveringSets - one entry per demanded t-tuple: the list of candidate indices (into candidates) that cover it; an empty inner list means no candidate covers that tuple (→ returns Optional.empty())
      Returns:
      the chosen minimal covering rows, or Optional.empty() if infeasible