CODEWITHSUNDEEP
constraint-programmingoptaplanner
Mene
Mene

Reputation: 3799

Solving equations as CSP

I have a set of equations. I also have a set of values and the results for the equation. Something like:

a + b + c = x

and some allocation might be:

1 + 1 + 1 = 3

2 + 3 + 4 = 9

However, the actual equations are much longer and may contain some functions, for example logarithms.

I now need to alter the result of a given set in a way that (1) the equation becomes equal to a specific value xx and (2) the parameters change as little as possible.

I thought I could solve this as a CSP by altering the eqation to

(a + ax) + (b + bx) + (c + cx) = xx

where a, b and c correspond to the old values and ax, bx and cx are the differences which need to be applied to the corresponding old values. And xx will be the result I want the equation to have. Note that a, b, c, xa, xb, cx etc. are all integer values and xx will always be within a certain distance to x, i.e. xx - d < x < xx + d.

In a CSP a, b, c and xx would be treated as Problem facts, ax, bx, cx would be treated as Planning variable and the equation (a + ax) + (b + bx) + (c + cx) = xx would be a hard constraint. Minimizing all of ax, ab, ac would be a soft constraint. I don't really see a Planning entity here.

global HardSoftScoreHolder scoreHolder;


rule "changeIsBad"
    when
        DeltaVariable($delta : delta)
    then
        scoreHolder.addSoftConstraintMatch(kcontext, -Math.abs(delta));
end

rule "equationMustBeEqual"
    // No idea?
end

But I can't figure out how to go on from here. Is Optaplanner feasible for this kind of problem? It seems all PlanningVariables have to come from a List and have to be instances, whereas I only have integer values. Is my model correct?

Upvotes: 0

Views: 279

Answers (1)

Geoffrey De Smet
Geoffrey De Smet

Reputation: 27312

You can wrap each integer variable in an entity class, like this:

@PlanningEntity
public class MyEntity {

   private Integer myVariable;

   @PlanningVariable(...)
   public Integer getMyVariable() {...}
   ...
}

Additionally, use a planning entity range to define the range of each variable (because it differs per entity), see official docs section "4.3.5.2.2. ValueRangeProvider on a planning entity" (and don't use SwapMove's, only ChangeMove's I guess).

But overall, I am not 100% sure if this is the right tool for the job. I would be interested to know what your experience with this use case results into.

PS: Starting from 6.1.0.Beta1 (not yet released, but nightlies are available), we have IntValueRange as documented in nightly docs in section "4.3.5.2.4. ValueRangeFactory", which is more efficient for these kinds of use cases.

Upvotes: 1

Related Questions