Module org.cicirello.chips_n_salsa
Package org.cicirello.search.problems

Class PolynomialRootFinding

java.lang.Object
org.cicirello.search.problems.PolynomialRootFinding
All Implemented Interfaces:
OptimizationProblem<SingleReal>, Problem<SingleReal>
public final class PolynomialRootFinding extends Object implements OptimizationProblem<SingleReal>
This class defines polynomial root finding as an optimization problem, enabling solving via simulated annealing or other metaheuristic optimization algorithms. In polynomial root-finding, we have an equation of the form: 0 = c0 + c1*x + c2*x2 + ... + cN*xN. The problem is to find a value of x, known as a root or as a zero, that satisfies the equation. This class represents root-finding as an optimization problem where one must find a value of x to minimize the value of: abs(c0 + c1*x + c2*x2 + ... + cN*xN).

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    static final double
    DEFAULT_PRECISION
    The default for the precision of the result.

  • Constructor Summary

    Constructors
    Constructor
    Description
    PolynomialRootFinding(double[] coefficients)
    Defines a problem for finding a root of a polynomial equation of the form: 0 = c0 + c1*x + c2*x2 + ...
    PolynomialRootFinding(double[] coefficients, double precision)
    Defines a problem for finding a root of a polynomial equation of the form: 0 = c0 + c1*x + c2*x2 + ...
    PolynomialRootFinding(double a, double b, double c)
    Defines a problem for finding a root of a quadratic equation of the form: 0 = a*x2 + b*x + c.
    PolynomialRootFinding(double a, double b, double c, double precision)
    Defines a problem for finding a root of a quadratic equation of the form: 0 = a*x2 + b*x + c.

  • Method Summary

    Modifier and Type
    Method
    Description
    double
    cost(SingleReal candidate)
    Computes the cost of a candidate solution to the problem instance.
    boolean
    isMinCost(double cost)
    Checks if a given cost value is equal to the minimum theoretical cost across all possible solutions to the problem instance, where lower cost implies better solution.
    double
    minCost()
    A lower bound on the minimum theoretical cost across all possible solutions to the problem instance, where lower cost implies better solution.
    double
    value(SingleReal candidate)
    Computes the value of the candidate solution within the usual constraints and interpretation of the problem.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

    Methods inherited from interface org.cicirello.search.problems.OptimizationProblem

    costAsDouble, getSolutionCostPair

  • Field Details

  • Constructor Details

    • PolynomialRootFinding

      public PolynomialRootFinding(double a, double b, double c)
      Defines a problem for finding a root of a quadratic equation of the form: 0 = a*x2 + b*x + c. The problem defined is to find a value of x that satisfies the above equation. Uses the DEFAULT_PRECISION for the precision of the result, i.e., any x such that DEFAULT_PRECISION ≥ abs( a*x2 + b*x + c).
      Parameters:
      a - The coefficient of the quadratic term.
      b - The coefficient of the linear term.
      c - The constant term.
      See Also:

    • PolynomialRootFinding

      public PolynomialRootFinding(double a, double b, double c, double precision)
      Defines a problem for finding a root of a quadratic equation of the form: 0 = a*x2 + b*x + c. The problem defined is to find a value of x that satisfies the above equation. Programmer can specify the precision of the result, i.e., finds any x such that precision ≥ abs( a*x2 + b*x + c).
      Parameters:
      a - The coefficient of the quadratic term.
      b - The coefficient of the linear term.
      c - The constant term.
      precision - The precision of the result.
      See Also:

    • PolynomialRootFinding

      public PolynomialRootFinding(double[] coefficients)
      Defines a problem for finding a root of a polynomial equation of the form: 0 = c0 + c1*x + c2*x2 + ... + cN*xN. The problem defined is to find a value of x that satisfies the above equation. Uses the DEFAULT_PRECISION for the precision of the result, i.e., any x such that DEFAULT_PRECISION ≥ abs(c0 + c1*x + c2*x2 + ... + cN*xN).
      Parameters:
      coefficients - An array of the coefficients of the polynomial. The degree of the polynomial is equal to coefficients.length - 1. The value of coefficients[i] is the coefficient of the xi term. Thus, coefficients[0] is the constant term. The length of coefficients must be at least 2.
      Throws:
      IllegalArgumentException - if coefficients.length < 2
      NullPointerException - if coefficients is null
      See Also:

    • PolynomialRootFinding

      public PolynomialRootFinding(double[] coefficients, double precision)
      Defines a problem for finding a root of a polynomial equation of the form: 0 = c0 + c1*x + c2*x2 + ... + cN*xN. The problem defined is to find a value of x that satisfies the above equation. Programmer can specify the precision of the result, i.e., finds any x such that precision ≥ abs(c0 + c1*x + c2*x2 + ... + cN*xN).
      Parameters:
      coefficients - An array of the coefficients of the polynomial. The degree of the polynomial is equal to coefficients.length - 1. The value of coefficients[i] is the coefficient of the xi term. Thus, coefficients[0] is the constant term. The length of coefficients must be at least 2.
      precision - The precision of the result.
      Throws:
      IllegalArgumentException - if coefficients.length < 2
      NullPointerException - if coefficients is null
      See Also:

  • Method Details

    • cost

      public double cost(SingleReal candidate)
      Description copied from interface: OptimizationProblem
      Computes the cost of a candidate solution to the problem instance. The lower the cost, the more optimal the candidate solution.
      Specified by:
      cost in interface OptimizationProblem<SingleReal>
      Parameters:
      candidate - The candidate solution to evaluate.
      Returns:
      The cost of the candidate solution. Lower cost means better solution.

    • minCost

      public double minCost()
      Description copied from interface: OptimizationProblem
      A lower bound on the minimum theoretical cost across all possible solutions to the problem instance, where lower cost implies better solution. The default implementation returns Double.NEGATIVE_INFINITY.
      Specified by:
      minCost in interface OptimizationProblem<SingleReal>
      Returns:
      A lower bound on the minimum theoretical cost of the problem instance.

    • isMinCost

      public boolean isMinCost(double cost)
      Checks if a given cost value is equal to the minimum theoretical cost across all possible solutions to the problem instance, where lower cost implies better solution.
      Specified by:
      isMinCost in interface OptimizationProblem<SingleReal>
      Parameters:
      cost - The cost to check.
      Returns:
      true if abs(cost) is ≤ precision.
      See Also:

    • value

      public double value(SingleReal candidate)
      Description copied from interface: OptimizationProblem
      Computes the value of the candidate solution within the usual constraints and interpretation of the problem.
      Specified by:
      value in interface OptimizationProblem<SingleReal>
      Parameters:
      candidate - The candidate solution to evaluate.
      Returns:
      The actual optimization value of the candidate solution.