|
|
equations.c File ReferenceImplementation of the functions operating on sets of Tequations. More... #include "equations.h" #include "defines.h" #include "error.h" #include "geom.h" #include <math.h> Go to the source code of this file.
Detailed DescriptionImplementation of the functions operating on sets of Tequations.
Definition in file equations.c. Function Documentation
Defines all the information associated with an equation.
Definition at line 220 of file equations.c. References AddTerm2LinearConstraint(), CIRCLE_EQUATION, CircleEquation(), CopyEquation(), DeleteEquation(), DeriveEquation(), TequationInfo::EqType, TequationInfo::equation, Error(), GENERAL_EQUATION, GetEquationCmp(), GetEquationValue(), GetEquationVariables(), GetMonomial(), GetMonomialCt(), GetMonomialVariables(), GetNumMonomials(), GetVariableN(), TequationInfo::Hessian, InitLinearConstraint(), TequationInfo::Jacobian, TequationInfo::lc, LINEAR_EQUATION, LinearEquation(), TequationInfo::n, NEW, NewInterval(), PARABOLA_EQUATION, ParabolaEquation(), SADDLE_EQUATION, SaddleEquation(), SetLinearConstraintError(), SimplexExpandBounds(), SPHERE_EQUATION, SphereEquation(), and VariableSetSize(). Referenced by AddEquation().
Here is the call graph for this function:
Here is the caller graph for this function:
Returns the equation stored in a TequationInfo.
Definition at line 332 of file equations.c. References TequationInfo::equation. Referenced by AddEquation(), AddEquation2Simplex(), CropEquation(), GetEquation(), GetEquationTypeN(), HasEquation(), IsCoordEquation(), IsDummyEquation(), IsSystemEquation(), LinearizeCircleEquation(), LinearizeGeneralEquation(), LinearizeGeneralEquationInt(), LinearizeParabolaEquation(), LinearizeSaddleEquation(), LinearizeSphereEquation(), and PrintEquations().
Here is the caller graph for this function:
Creates a TequationInfo copying data from another TequationInfo.
Definition at line 337 of file equations.c. References CopyEquation(), CopyLinearConstraint(), TequationInfo::EqType, TequationInfo::equation, TequationInfo::Hessian, TequationInfo::Jacobian, TequationInfo::lc, LINEAR_EQUATION, TequationInfo::n, and NEW. Referenced by CopyEquations().
Here is the call graph for this function:
Here is the caller graph for this function:
Defines a first order approximation to a given equation from the information we have of this equation.
Definition at line 379 of file equations.c. References AddTerm2LinearConstraint(), TequationInfo::equation, EvaluateEquationInt(), GetBoxIntervals(), GetBoxMaxSizeVarSet(), GetBoxNIntervals(), GetEquationValue(), GetEquationVariables(), GetVariableN(), TequationInfo::Hessian, INF, InitLinearConstraint(), IntervalAdd(), IntervalInvert(), IntervalOffset(), IntervalPow(), IntervalProduct(), IntervalScale(), TequationInfo::Jacobian, LowerLimit(), TequationInfo::n, NEW, NewInterval(), SetLinearConstraintError(), and ZERO. Referenced by CropEquation(), and LinearizeGeneralEquationInt().
Here is the call graph for this function:
Here is the caller graph for this function:
Computes the linealization error for a given equation for each variable involved in the equation.
Definition at line 512 of file equations.c. References TequationInfo::EqType, TequationInfo::equation, GetEquationVariables(), GetVariableN(), TequationInfo::Hessian, IntervalAdd(), IntervalOffset(), IntervalPow(), IntervalProduct(), IntervalScale(), IntervalSize(), LINEAR_EQUATION, TequationInfo::n, NEW, and NewInterval(). Referenced by UpdateSplitWeight().
Here is the call graph for this function:
Here is the caller graph for this function:
Produces a linear relaxation for a saddle equation z=x*y. It consists of four planes each derived from a linealization of the saddle funcion at the corners of the x-y box.
Definition at line 1212 of file equations.c. References GEQ, GetBoxIntervals(), GetBoxNIntervals(), GetMonomial(), GetMonomialVariables(), GetOriginalEquation(), GetVariableN(), LEQ, LinearizeGeneralEquationInt(), LowerLimit(), NEW, TRUE, and UpperLimit(). Referenced by AddEquation2Simplex().
Here is the call graph for this function:
Here is the caller graph for this function:
Produces a linear relaxation for a parabola equation y=x^2. It consists of two lines derived from a linear approximation of the parabola at the center of the x interval. Additionaly, we define linear constraints on the extremes of the range of x.
Definition at line 1267 of file equations.c. References EQU, GetBoxIntervals(), GetBoxNIntervals(), GetMonomial(), GetMonomialVariables(), GetOriginalEquation(), GetVariableN(), IntervalCenter(), LEQ, LinearizeGeneralEquationInt(), LowerLimit(), NEW, TRUE, and UpperLimit(). Referenced by AddEquation2Simplex().
Here is the call graph for this function:
Here is the caller graph for this function:
Produces a linear relaxation for a circle equation x^2+y^2=r^2. It consists of two lines derived from a linear approximation of the circle at the center of the x-y box. Additionaly, we define linear constraints for the corners of the x-y box that are out of the circle.
Definition at line 1317 of file equations.c. References GetBoxIntervals(), GetBoxNIntervals(), GetEquationCmp(), GetEquationValue(), GetEquationVariables(), GetOriginalEquation(), GetVariableN(), IntervalCenter(), LEQ, LinearizeGeneralEquationInt(), LowerLimit(), NEW, ROUNDDOWN, ROUNDNEAR, TRUE, and UpperLimit(). Referenced by AddEquation2Simplex().
Here is the call graph for this function:
Here is the caller graph for this function:
Produces a linear relaxation for a sphere equation x^2+y^2*z^2=r^2. It consists of two lines derived from a linear approximation of the sphere at the center of the x-y-z box. Additionaly, we define linear constraints for the corners of the x-y-z box that are out of the sphere.
Definition at line 1414 of file equations.c. References EQU, GetBoxIntervals(), GetBoxNIntervals(), GetEquationValue(), GetEquationVariables(), GetOriginalEquation(), GetVariableN(), IntervalCenter(), LEQ, LinearizeGeneralEquationInt(), LowerLimit(), NEW, ROUNDDOWN, ROUNDNEAR, TRUE, and UpperLimit(). Referenced by AddEquation2Simplex().
Here is the call graph for this function:
Here is the caller graph for this function:
Produces a linear relaxation for a general equation. It consists of two lines derived from a linear approximation of the equation at the given point.
Definition at line 1522 of file equations.c. References DeleteLinearConstraint(), GetBoxIntervals(), GetBoxMaxSizeVarSet(), GetEquationVariables(), GetFirstOrderApproximationToEquation(), GetOriginalEquation(), INF, SimplexAddNewConstraint(), and TRUE. Referenced by LinearizeCircleEquation(), LinearizeGeneralEquation(), LinearizeParabolaEquation(), LinearizeSaddleEquation(), and LinearizeSphereEquation().
Here is the call graph for this function:
Here is the caller graph for this function:
Produces a linear relaxation for a general equation at the central point of the sub-box defined by the variables involved in the equation using LinearizeGeneralEquationInt.
Definition at line 1545 of file equations.c. References GetBoxIntervals(), GetBoxNIntervals(), GetEquationCmp(), GetEquationVariables(), GetOriginalEquation(), GetVariableN(), INF, IntervalCenter(), LinearizeGeneralEquationInt(), LowerLimit(), TequationInfo::n, NEW, and UpperLimit(). Referenced by AddEquation2Simplex().
Here is the call graph for this function:
Here is the caller graph for this function:
Deletes the equation information stored in the and frees the allocated memory space.
Definition at line 567 of file equations.c. References DeleteEquation(), DeleteLinearConstraint(), TequationInfo::EqType, TequationInfo::equation, TequationInfo::Hessian, TequationInfo::Jacobian, TequationInfo::lc, LINEAR_EQUATION, and TequationInfo::n. Referenced by DeleteEquations().
Here is the call graph for this function:
Here is the caller graph for this function:
Initializes a set of equations.
Definition at line 595 of file equations.c. References Tequations::c, Tequations::d, Tequations::e, Tequations::equation, INIT_NUM_EQUATIONS, Tequations::max, Tequations::n, NEW, and Tequations::s. Referenced by DummifyCuikSystem(), GaussianElimination(), InitCuikSystem(), RemoveEquationsWithVar(), and ReplaceVariableInEquations().
Here is the caller graph for this function:
Initializes a set of equations from another set.
Definition at line 611 of file equations.c. References Tequations::c, CopyEquationInfo(), Tequations::d, Tequations::e, Tequations::equation, Tequations::max, Tequations::n, NEW, and Tequations::s. Referenced by CopyCuikSystem(), CuikSystemMerge(), DummifyCuikSystem(), GaussianElimination(), GetCSEquations(), RemoveEquationsWithVar(), ReplaceVariableInEquations(), and SimplifyCuikSystem().
Here is the call graph for this function:
Here is the caller graph for this function:
Checks if a variable is used in non-dummy equations of the set of equations.
Definition at line 637 of file equations.c. References DUMMY_EQ, FALSE, GetEquation(), GetEquationType(), GetEquationVariables(), and VarIncluded(). Referenced by CSRemoveUnusedVars().
Here is the call graph for this function:
Here is the caller graph for this function:
Checks if a variable is used in the set of equations.
Definition at line 657 of file equations.c. References FALSE, GetEquation(), GetEquationVariables(), and VarIncluded(). Referenced by CSRemoveUnusedVars(), and SampleCuikSystemInBox().
Here is the call graph for this function:
Here is the caller graph for this function:
Removes all equations that include a given variable. This is one of the steps to remove a variable from a problem. Therefore, equations that do not include the given variable are also affected by this function: we have to shift all the variable indexes higher than the given one. The use of this function without using function RemoveVariable right immediately after it leaves the cuiksystem in a incoherent state.
Definition at line 673 of file equations.c. References AddEquation(), CopyEquations(), DeleteEquations(), FixVariableInEquation(), GetEquation(), GetEquationVariables(), InitEquations(), Tequations::n, and VarIncluded(). Referenced by CSRemoveUnusedVars().
Here is the call graph for this function:
Here is the caller graph for this function:
Replaces a variable by linear combination of variables (including an offset). The use of this function without using function RemoveVariable right immediately after it leaves the cuiksystem in a incoherent state.
Definition at line 702 of file equations.c. References AddEquation(), CopyEquations(), DeleteEquations(), FALSE, GetEquation(), InitEquations(), ReplaceVariableInEquation(), and TRUE. Referenced by CSRemoveLCVars(), and CSRemoveVarsWithCtRange().
Here is the call graph for this function:
Here is the caller graph for this function:
Operates linearly pairs of equations (scale one of the and then sum them) with the objective of getting a simpler equation (i.e., one with less monomials). The rationale is that equations with less monomials produce simpler problems and, in some cases, they can trigger simplifications that are not evident at first sight. The use of this function without using function RemoveVariable right immediately after it leaves the cuiksystem in a incoherent state.
Definition at line 737 of file equations.c. References AccumulateEquations(), AddEquation(), CopyEquation(), CopyEquations(), DeleteEquation(), DeleteEquations(), DUMMY_EQ, EQU, FALSE, FindMonomial(), GetEquation(), GetEquationCmp(), GetEquationNumVariables(), GetEquationType(), GetMonomial(), GetMonomialCt(), GetNumMonomials(), InitEquations(), NEquations(), NO_UINT, and TRUE. Referenced by SimplifyCuikSystem().
Here is the call graph for this function:
Here is the caller graph for this function:
Number of equations in the set.
Definition at line 829 of file equations.c. References Tequations::n. Referenced by CoordInequalitiesHold(), CSRemoveLCVars(), CuikSystemMerge(), DeleteCuikSystemJacobian(), DummifyCuikSystem(), ErrorInInequalities(), ErrorInSolution(), GaussianElimination(), GetCSNumEquations(), GetCuikSystemJacobian(), and UpdateCuikSystem().
Here is the caller graph for this function:
Number of system equations in the set.
Definition at line 834 of file equations.c. References Tequations::s.
Number of coordenalization equations in the set.
Definition at line 839 of file equations.c. References Tequations::c.
Number of dummy equations in the set.
Definition at line 844 of file equations.c. References Tequations::d.
Number of equality equations in the set.
Definition at line 849 of file equations.c. References Tequations::e. Referenced by UpdateCuikSystem().
Here is the caller graph for this function:
Identify system equations.
Definition at line 854 of file equations.c. References Tequations::equation, GetEquationType(), GetOriginalEquation(), and SYSTEM_EQ. Referenced by PrintEquations().
Here is the call graph for this function:
Here is the caller graph for this function:
Identify coordenalization equations.
Definition at line 860 of file equations.c. References COORD_EQ, Tequations::equation, GetEquationType(), and GetOriginalEquation(). Referenced by PrintEquations().
Here is the call graph for this function:
Here is the caller graph for this function:
Identify dummy equations.
Definition at line 866 of file equations.c. References DUMMY_EQ, Tequations::equation, GetEquationType(), and GetOriginalEquation(). Referenced by PrintEquations().
Here is the call graph for this function:
Here is the caller graph for this function:
Gets the type of a particular equation.
Definition at line 872 of file equations.c. References Tequations::equation, GetEquationType(), GetOriginalEquation(), and NOTYPE_EQ.
Here is the call graph for this function:
Checks if a given equation is already in the set.
Definition at line 880 of file equations.c. References CmpEquations(), Tequations::equation, FALSE, and GetOriginalEquation(). Referenced by AddEquation().
Here is the call graph for this function:
Here is the caller graph for this function:
Gets a box (as an array of parameters is of size m) and uses the equation number ne to reduce the ranges of the variables involved in the equation as much as possible.
Definition at line 895 of file equations.c. References BoxSaddleClipping(), BoxSphereClipping(), CIRCLE_EQUATION, CopyInterval(), CropLinearConstraint(), DeleteLinearConstraint(), EMPTY_BOX, TequationInfo::EqType, EQU, Tequations::equation, Error(), GENERAL_EQUATION, GetBoxIntervals(), GetBoxNIntervals(), GetEquationCmp(), GetEquationValue(), GetEquationVariables(), GetFirstOrderApproximationToEquation(), GetLinearConstraintError(), GetMonomial(), GetMonomialCt(), GetMonomialVariables(), GetNumMonomials(), GetOriginalEquation(), GetVariableN(), INF, IntervalCenter(), IntervalSize(), TequationInfo::lc, LINEAR_EQUATION, TequationInfo::n, NEW, NewInterval(), NOT_REDUCED_BOX, PARABOLA_EQUATION, PrintEquation(), PrintInterval(), RectangleCircleClipping(), RectangleParabolaClipping(), REDUCED_BOX, SADDLE_EQUATION, SetLinearConstraintError(), SimplexExpandBounds(), SPHERE_EQUATION, VariableSetSize(), and ZERO. Referenced by AddEquation2Simplex(), and ReduceBoxEquationWise().
Here is the call graph for this function:
Here is the caller graph for this function:
Adds an equation to the set and computes its associated information.
Definition at line 1157 of file equations.c. References Tequations::c, CmpEquations(), COORD_EQ, Tequations::d, DUMMY_EQ, Tequations::e, EQU, Tequations::equation, Error(), GetEquationCmp(), GetEquationType(), GetNumMonomials(), GetOriginalEquation(), HasEquation(), Tequations::max, MEM_DUP, Tequations::n, NEW, NOCMP, NormalizeEquation(), NOTYPE_EQ, Tequations::s, SetEquationInfo(), and SYSTEM_EQ. Referenced by AddEquation2CS(), DummifyAndAddEquation(), GaussianElimination(), RemoveEquationsWithVar(), and ReplaceVariableInEquations().
Here is the call graph for this function:
Here is the caller graph for this function:
Returns a pointer to the n-th equation stored in the set.
Definition at line 1204 of file equations.c. References Tequations::equation, and GetOriginalEquation(). Referenced by ComputeSimpCuikSystemJacobian(), CoordInequalitiesHold(), CSRemoveLCVars(), CuikSystemMerge(), DummifyCuikSystem(), ErrorInInequalities(), ErrorInSolution(), GaussianElimination(), GetCSEquation(), GetCuikSystemJacobian(), RemoveEquationsWithVar(), ReplaceVariableInEquations(), UsedVarInEquations(), and UsedVarInNonDummyEquations().
Here is the call graph for this function:
Here is the caller graph for this function:
Adds linear constraints representing the selected equation (i.e., a linear relaxation of the equation) to a simplex tableau. Linear constraints are directly added to the simplex using the information cached in the TequationInfo structure. Non linear equations are linearized using the information stored in the Jacobian and Hessian fields in the corresponding TequationInfo too. Different equations are linearized in a different way
By using small lr2tm_q and lr2tm_s we generate linear relaxations that tightly bound the functions and this reduces the number of iterations to found the solution. The drawnback is that we we add more constraints to the simplex and this slows downs each iteration. Equations that define particular variables (cartesian or dummy ones) are only added to the simplex if the variable is used in any of the other constraints already in the simplex. Otherwise we will add useless constraints. This filter is implemented with the array of booleans usedVar. This array is updated as we add equations to the simplex and is checked to see if defined variables are used before adding the corresponding equation to the simplex. For this to be operative, equations are ordered so that system equations are added first to the simplex, then cartesian equations and, finally, dummyfications equations. There is no need to equations that involves almost constant variables to the simplex. Thus, before adding an EQU equation to the simplex, we evaluate the equations using interval arithmetics and if the result is almost constant(this occurs if the variables involved in the equation are have tiny ranges) we just check if the equation holds or not. If not, the system has no solution. The same applies to inequalities that already hold. An inequality (LEQ, GEQ equations) that trivially holds do not add any constrain to the simplex and, consequently we do not add it to the Tableau.
Definition at line 1584 of file equations.c. References CIRCLE_EQUATION, CropEquation(), EMPTY_BOX, TequationInfo::EqType, EQU, Tequations::equation, Error(), EvaluateEquationInt(), FALSE, GENERAL_EQUATION, GEQ, GetBoxIntervals(), GetBoxMinSizeVarSet(), GetEquationCmp(), GetEquationValue(), GetEquationVariables(), GetOriginalEquation(), INF, IntervalOffset(), IntervalSize(), IsInside(), TequationInfo::lc, LEQ, LINEAR_EQUATION, LinearizeCircleEquation(), LinearizeGeneralEquation(), LinearizeParabolaEquation(), LinearizeSaddleEquation(), LinearizeSphereEquation(), LowerLimit(), PARABOLA_EQUATION, PrintEquation(), PrintInterval(), SADDLE_EQUATION, SimplexAddNewConstraint(), SPHERE_EQUATION, TRUE, and UpperLimit(). Referenced by ReduceBox().
Here is the call graph for this function:
Here is the caller graph for this function:
When the SPLIT_ERROR parameter is set to TRUE, we select the split variable for a box from the linearization error induced by the variables. This function updates the error induced by the variables in a given equation.
Definition at line 1775 of file equations.c. References TequationInfo::EqType, TequationInfo::equation, Tequations::equation, ErrorDueToVariable(), GetBoxIntervals(), GetBoxNIntervals(), GetEquationVariables(), GetVariableN(), IntervalCenter(), LINEAR_EQUATION, TequationInfo::n, and NEW. Referenced by ComputeSplitDimInt().
Here is the call graph for this function:
Here is the caller graph for this function:
Writes a set of equations into a stream.
Definition at line 1819 of file equations.c. References Tequations::c, Tequations::d, Tequations::equation, GetOriginalEquation(), IsCoordEquation(), IsDummyEquation(), IsSystemEquation(), Tequations::n, PrintEquation(), and Tequations::s. Referenced by CSRemoveLCVars(), CSRemoveVarsWithCtRange(), PrintCuikSystem(), PrintCuikSystemWithSimplification(), and SimplifyCuikSystem().
Here is the call graph for this function:
Here is the caller graph for this function:
Deletes the information stored in the set of equations and frees the allocated memory space.
Definition at line 1854 of file equations.c. References Tequations::c, Tequations::d, DeleteEquationInfo(), Tequations::e, Tequations::equation, Tequations::n, and Tequations::s. Referenced by DeleteCuikSystem(), DummifyCuikSystem(), GaussianElimination(), RemoveEquationsWithVar(), ReplaceVariableInEquations(), and UnUpdateCuikSystem().
Here is the call graph for this function:
Here is the caller graph for this function:
|