10
$\begingroup$

I've regularly encountered that there are too many constraints to categorize into just hard and soft constraints. For example:

  • Physical constraints (very hard), e.g. 1 person can only be at 1 spot at the same time
  • Legal constraints (hard), e.g. 1 person can only do 1 shift per day
  • Unassigned constraints (less hard), e.g. each shift must be assigned (broken during overconstrained planning)
  • Non-disruptive constraints (even less hard), e.g. don't change the schedule unless it's to avoid breaking harder constraints given the input change
  • Monetary constraints (soft), e.g. fuel consumption in VRP
  • Fairness constraints (very soft or less soft depending on enterprise or government case), e.g. distribution of total workload per employee

Obviously, physical constraints can't be broken. Legal constraints can't be broken either - unless of course you risk people dying (unassigned shifts in intensive care). And the lower hard constraints shouldn't be broken normally either, but it does happen... so I prefer to call those medium constraints. In any case, there's clear priority between these constraint levels - and still each level (such as monetary constraints) might have multiple normally weighted constraints.

One common way I've seen in the literature to deal with such cases is to multiply the priority constraint by a big weight and add it into the fitness function alongside the lower priority constraint.

What is the canonical name of this practice?

I've started calling this practice Score Folding in the OptaPlanner manual, but I've not seen that term used anywhere else, so I am wondering if there's a consensus for it that I should use instead.

Note that I am not a fan of Scoring Folding, to say the least. I've introduced for multi score level support a decade ago, to avoid it, as the big weight can easily cause invalid behavior with the wrong dataset, being too big, or too small, or both (even with 64 bit numbers).

Here's an illustration:

score folding

In the example above, we're folding a harder and a softer constraint into the soft score. The harder constraint is the number of CPU too little. The softer constraint is the maintenance price of each computer.

Improve this question
$\endgroup$
3
  • $\begingroup$ Are you aware of Lagrangian Relaxation and Lagrange Multipliers? This seems to be somewhat related. $\endgroup$
    – Michael Feldmeier
    Jun 3, 2019 at 20:06
  • $\begingroup$ Is it correct if I understand your question as "I am trying to solve a constraint optimization problem using metaheuristics that can't handle constraints, so I have to relax all of them. However some of the constraints absolutely have to be satisfied, while others should be, but don't have to. I am doing this by applying different penalties to each relaxed term. How is is this process of handling constraints called in the literaure?" $\endgroup$
    – Michael Feldmeier
    Jun 4, 2019 at 18:54
  • 1
    $\begingroup$ @MichaelFeldmeier Maybe, there is no need to relax the physical and legal constraints, in any case. All of the 4 other examples of constraints are - in an LP state of mind - part of the fitness function, as they might indeed be broken (some in very rare occasions). But they should only be broken lexicographical: don't break any of the higher priority constraints if you can avoid it by breaking tons of the lower priority constraints. $\endgroup$
    – Geoffrey De Smet
    Jun 4, 2019 at 19:25

4 Answers 4

Reset to default
8
$\begingroup$

It's not exactly the same thing, but very close: in goal programming, using a weighted combination of the deviations from goals is often called "Archimedean" (as in "Archimedean" goal programming, or using "Archimedean weights"). I'm not sure what the origin of that was. An example appears here.

Improve this answer
$\endgroup$
2
  • $\begingroup$ It seems 'Archimedean' is due to the Archimedean property on the priority scheme. The lexicographic scheme is non-Archimedean in the sense that lower priority levels are infinitesimal to the next: no summation of lower priority goals can get a total priority larger than any higher priority. In contrast, Archimedean weights do satisfy their eponymous property: multiple lower priority goals can be combined to surpass a single higher priority goal (as long as there are enough goals to sum, of course). $\endgroup$
    – Discrete lizard
    Jun 17, 2019 at 11:37
  • 1
    $\begingroup$ So in that sense, something like 'Archimedean scoring' seems a good description of this practice, here, as the difference between a 'normal' priority based scoring scheme seems to be mainly the Archimedean property. $\endgroup$
    – Discrete lizard
    Jun 17, 2019 at 11:39
7
$\begingroup$

The act of moving soft constraint into the objective function using penalties is closely related to Lagrangian Relaxation and Lagrangian Multipliers.

The method penalizes violations of [...] constraints using a Lagrange multiplier, which imposes a cost on violations. These added costs are used instead of the strict [...] constraints in the optimization. In practice, this relaxed problem can often be solved more easily than the original problem.

In a comment you clarified: You are solving an optimization problem with different levels of soft constraints. You want to satisfy them lexicographically, i.e. hard(er) constraints take priority over soft(er) constraints.

I suggest you solve your model multiple times. In the first pass, include only the absolutely necessary constraints. If it turns out to be infeasible already, you've got your answer. If it is feasible, include the next level constraint and re-optimize. If you still got a feasible solution, continue.

Eventually you will have a solution that satisfies as many soft constraints as possible.

Improve this answer
$\endgroup$
1
  • $\begingroup$ This approach doesn't guarantee satisfying as many soft constraints as possible. Suppose you have 100 constraints for each of level 1, 2, and 3 priority, and it's possible to satisfy all of them, except for one of the level 2 constraints which can never be satisfied. Under this approach, you would stop as soon as you hit the infeasible constraint at level 2, and end up with a solution that only respects the level 1 constraints, even though it would be possible to satisfy all of the 3s and nearly all of the 2s. $\endgroup$
    – GB supports the mod strike
    Jun 18, 2019 at 2:31
4
$\begingroup$

I’m not sure I’ve heard a canonical name, but that sounds like a multi-objective optimization problem where you’re minimizing the sum of weighted deviations. The weights are based on the constraint priorities. I’ve run into this a lot with nurse scheduling models - eg many types of constraints that can’t all be simultaneously satisfied (eg union rules, staff preferences, hospital requirements) and have different abilities to be violated.

As Rob and Michael mentioned there may be other ways to solve your problem. Depends on your requirements and your current method may be just fine. If you do want to mix it up, another framework you may want to consider is lexicographic goal programming.

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ I didn't mean to suggest a need for multi-objective optimization or pareto optimization: in this use case, for each constraint, it is exactly known how much more important it is than the other constraints. If they're on the same score level (for example both "soft"), they they both have a soft weight. If they on a different score level (for example one "medium" and one "soft"), then the higher level will always outweigh the lower one (so 1 medium is more important than 9 999 999 999 soft). $\endgroup$
    – Geoffrey De Smet
    Jun 4, 2019 at 19:17
  • $\begingroup$ Ok. To clarify a bit, I intended that the score levels are the known OF coefficients (weights), and the variables are how many times each constraint is violated. Because the hard level is weighted much higher in the OF, it won’t be violated unless many soft constraints are violated. And I’ve seen this referred to as “minimizing the sum of weighted deviations” but haven’t seen an actual name. Agreed if you know the coef, there’s no need to generate trade-off curves. Also if you/others have a good name for this, Id gladly adopt! $\endgroup$
    – E. Tucker
    Jun 4, 2019 at 21:02
4
$\begingroup$

One common way I've seen in the literature to deal with such cases is to multiply the priority constraint by a big weight and add it into the fitness function alongside the lower priority constraint.

You are likely to want greater complexity than that, see below.

What is the canonical name of this practice?

Suggestion: representation of a category.

A Hasse Diagram can be used to represent functions between special types of orders.

Your "very hard" constraints might be absolute, but your "hard" constraints might have numerous exceptions (does not apply in some places, to some people, at certain times of day, or where you would be held blameless such as the Good Samaritan Law).

Similarly your "very soft" constraint example (distribution of workload) could become absolute if the person quit. Even your "soft" constraint (fuel and vehicle routing problems) is subject to correct operation of the gauges and road construction.

Having a way to hold all the values and perform calculations to shift the values and weighs dynamically is important. You might chose to derive a Skew Tableaux from the matrices and traverse it in order, based on the re-ordering of your constraints after correctly calculating the weights dynamically and determining the overlap of the partially ordered sets.

A representation, such as Birkhoff's Representation Theorem, is the formal word used to describe sets that have been redefined (reordered) by their weight and interaction.

"In mathematics, representation is a very general relationship that expresses similarities between objects. Roughly speaking, a collection $Y$ of mathematical objects may be said to represent another collection $X$ of objects, provided that the properties and relationships existing among the representing objects $y_i$ conform in some consistent way to those existing among the corresponding represented objects $x_i$. Somewhat more formally, for a set $\Pi$ of properties and relations, a $\Pi$-representation of some structure $X$ is a structure $Y$ that is the image of $X$ under a homomorphism that preserves $\Pi$. The label representation is sometimes also applied to the homomorphism itself.".

"Homomorphisms of vector spaces are also called linear maps, and their study is the object of linear algebra. The concept of homomorphism has been generalized, under the name of morphism, to many other structures that either do not have an underlying set, or are not algebraic. This generalization is the starting point of category theory".

Perhaps, in your case, you would use "Representative Score" instead of "Score Folding".

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.