Problems with constraints

[ajnebro]

The issue

The definition of multi-objective problem states that a problem can have constraints, which will have to be managed somehow by the optimizer to deal with them.

The approach in jMetal is to include in the Problem interface a method to know how many constraints a problem has:

public interface Problem<S extends Solution<?>> extends Serializable {
  /* Getters */
  public int getNumberOfVariables() ;
  public int getNumberOfObjectives() ;
  public int getNumberOfConstraints() ;
  public String getName() ;

  /* Methods */
  public void evaluate(S solution) ;
  public S createSolution() ;
}

By default, getNumberOfConstraints() must return 0 if the problem has no constraints.

To define a constrained problem, it must implement the ConstrainedProblem interface:

public interface ConstrainedProblem<S extends Solution<?>> extends Problem<S> {

 /* Getters */
  public int getNumberOfConstraints() ;

  /* Methods */
  public void evaluateConstraints(S solution) ;
}

Discusion

When writing the documentation of the Problem interface I explained how to evaluate a solution:

DoubleProblem problem ;
DoubleSolution solution ;

problem.evaluate(solution);
if (problem instanceof ConstrainedProblem) {
  ((ConstrainedProblem<DoubleSolution>) problem).evaluateConstraints(solutionn);
}

and I disliked a lot the need of having to do use instanceof whenever a solution is evaluated. I didn't paid attention to this before because most of the solution evaluations were encapsulated in evaluator classes.

Alternative

As I mentioned in the documentation, an alternative to dealing with constraints is simply to define that the evaluate() method not only evaluates the objective function but also the constraints. This way there is no need of a ConstrainedProblem interface and we avoid possible errors related to forget to call evaluateConstraints().

[ajnebro]

After discusing the issue with Juanjo, there is a lack of flexilibity in the alternative approach: there can be some situations where a solution can be discarded if some constraints are not fulfilled, thus avoiding the need of evaluating it. This could be the case of a real-world problem having costly evaluation functions.

The issue is still open then ... Note that in the former NSGAII versions all the problems had theevaluate() and evaluateConstraints() methods, being the latter defined by returning 0 by default in the case of problems without constraints.

[matthieu-vergne]

Definition

We already had a discussion about variables and objectives being managed as attributes. Why not do the same for constraints? evaluate() may include the full process, as you mention in your alternative, and for me it would make sense.

Regarding the fact that some solutions may be discarded, is it really your point here? The problem is not the one which chooses how the solutions not fitting the constraints are used, this is the algorithm. The constraints provided by the problem only say that the final solution(s) should fit these constraints. The algorithm may first evaluate the constraints and discard the solutions not fitting enough, then evaluate them and discard the solutions not being good enough.

The main difference I see between an objective and a constraint is that the objective gives an order (some are better than others) while constraints give a filter (it fits or not), which is just a simple order with only two positions (high/low). But if you want to be more expressive, you may consider to say how much it fits instead of a binary answer. This would make sense if you want to use your ConstraintViolationComparator. So what appears to me is that what you call a "constraint" now is actually a combination of:

• an attribute evaluation (result in a set of values)
• a filter on this attribute (binary result, fits or not)

Implementation

Naive compliance to the Definition

As a first attempt, we may gain clarity in replacing these methods:

public int getNumberOfVariables() ;
public int getNumberOfObjectives() ;
public int getNumberOfConstraints() ;

by:

public Collection<Variable<Solution,?>> getVariables() ;
public Collection<Objective<Solution,?>> getObjectives() ;
public Map<Objective<Solution,?>,Constraint<Solution,?>> getConstraints() ;

I reuse here the notions of Variable and Objective described in the same discussion than the one cited above. If you want the number of X (variables/objectives/constraints), just use getX().size(). What is new here is getConstraints() which builds on the objectives: objectives give values, while constraints map these objectives to specific limits. A Constraint may look like a simple filter:

public interface Constraint<Solution, Value> {
  public boolean fits(Solution solution, Objective<Solution, Value> objective);
}

so it gets the value of the objective for the given solution and tells whether or not it fits. With such a design, there is no ConstrainedProblem. Each problem may have constraints if getConstraints() returns a non-empty collection, and the level of violation may be considered by looking at the values of the corresponding objectives.

The idea is simple and draws on separating the attribute evaluation and the filtering, but some drawbacks may arise: some constraints may be more complex, like considering several objectives at once, or even variables (e.g. this attribute fits with this value as long as this other attribute has this value), so this design may be too reduced. You may create combined objectives specifically for constraints, but then it would be arguable to provide them as objectives themselves because they are redundant.

More Flexible

This design may be then more suitable:

public Collection<Variable<Solution,?>> getVariables() ;
public Collection<Objective<Solution,?>> getObjectives() ;
public Collection<Constraint<Solution>> getConstraints() ;

with this definition of constraint:

public interface Constraint<Solution> {
  public boolean fits(Solution solution);
}

Here we do not explicitely say what should be used, which means that the constraint should already know it. And this makes sense: if the problem is the one which provides the variables, the objectives, and the constraints, then it should have all the required information already to implement them properly. If in the future you make some separations, like a constrained problem building on an unconstrained one, then surely you should already know which variables and objectives are provided by the unconstrained problem before to setup your constraints. Creating constraints while you don't know yet what data you will have to deal with makes no sense. So it still works with this design.

However, we now miss the ability to know how much it fits to use comparators (we don't know anymore which objective to use). So instead of a boolean value, we may return a more expressive one:

public interface Constraint<Solution> {
  public double evaluateViolation(Solution solution);
}

wich returns zero when it fits and a strictly positive value when it does not, such that this value represents the level of violation of the solution for the given constraint.

Going Further

We could go further by separating variable and objective constraints, such that variable constraints tell you when a solution makes sense at all (objectives may be impossible to compute otherwise) while objective constraints relate to requirements for minimal quality. So you may:

1. create a solution,
2. ensure that it can be evaluated by ensuring that no variable constraint is violated,
3. evaluate the objectives,
4. clean based on the objective constraints to keep only the relevant ones.

evaluate() would focus on the point 3, while the point 2 may be considered directly in the solution creation (e.g. crossover which re-tries until it provides a valid solution) or act as an intrermediary step in higher level implementations (if the new solution(s) violates variable constraints, just drop the current iteration and pass to the next one).

[matthieu-vergne]

Regarding the variable constraints, it is just a rough idea. The point is to have valid solutions, so it overlaps (regarding its responsibilities) with the solution builder. I don't think that variable constraints would be the best design, but it may feed the discussion.

[ajnebro]

In that discusion I comented that the idea of having variables and objectives in this way:

public interface Variable<Solution, Value> {
  public void set(Solution solution, Value value);
  public Value get(Solution solution);
}

public interface Objective<Solution, Value> {
  public Value get(Solution solution);
}

were attractive to me, and this proposal is also interesting:

public Collection<Variable<Solution,?>> getVariables() ;
public Collection<Objective<Solution,?>> getObjectives() ;
public Collection<Constraint<Solution>> getConstraints() ;

I'm going to think about them. What I wouldn't like is to have to define classes such as DoubleVariable, IntegerVariable and so on and then to have to associate them to DoubleSolution, `IntegerSolution, etc. This is basically the same approach of former jMetal versions and we discarded it.

[matthieu-vergne]

This is normally not required: you have to specify the values of the generics. With your initial designs, all your variables were of the same type (e.g. DoubleSolution only have double values), which would correspond to this design (or something similar):

public Collection<Variable<Solution,Double>> getVariables() ;
public Collection<Objective<Solution,?>> getObjectives() ;
public Collection<Constraint<Solution>> getConstraints() ;

If you keep ? then you need to assume that it is of a given type and cast. Same problem with objectives: with this design we don't know which values are provided by the objectives. This could be solved by adding generics:

public Collection<Variable<Solution,VariableValue>> getVariables() ;
public Collection<Objective<Solution,ObjectiveValue>> getObjectives() ;
public Collection<Constraint<Solution>> getConstraints() ;

but it does not help when you have heterogeneous variables or objectives, which is prone to happen in real cases so I would not recommend it.

Surely, we need to think a bit about where such information is needed and how to organize it, but you should not need anymore DoubleSolution and similar stuff.

[Vavou]

Hi,

I hope, I'm not disturbing the debate but I don't find how to solve my problem: how to discard solution which have violated some constraints ?

I'm quite embarrassing because my final population contains lots of unrealisable solutions and I did not find a elegant way to discard its.

Thanks for your help

[ajnebro]

Hi Vavou. The constraint handling mechanism included in jMetal penalizes those solutions violating constraints (they are considered as soft constraints) but, depending on the problem, it is possible that an algorithm cannot find any feasible solution.

If you don't want to have unfeasible solutions an approach is to repair them after a crossover or mutation.

Antonio

[matthieu-vergne]

A bit out of topic, though. If the discussion need to go further, please open a dedicated issue, because we are speaking about the revision of the architecture of jMetal.

2016-04-28 15:47 GMT+02:00 Antonio J. Nebro notifications@github.com:

Hi Vavou. The constraint handling mechanism included in jMetal penalizes those solutions violating constraints (they are considered as soft constraints) but, depending on the problem, it is possible that an algorithm cannot find any feasible solution.

If you don't want to have unfeasible solutions an approach is to repair them after a crossover or mutation.

Antonio

— You are receiving this because you commented. Reply to this email directly or view it on GitHub https://github.com/jMetal/jMetal/issues/109#issuecomment-215428828

[Vavou]

Thank you @ajnebro for your answer and your propositions to solve mi problem. My apologizes for disturbing the topic

[ajnebro]

You are welcome.

No need for apologizing, of course :)