Suppose have an n queens problem like this, with n = 4 and 4 queens (A, B, C and D) on a 4*4 chessboard:

AB--
--C-   
---D
----

then a Local Search could move queen A, B, C or D.

Notice how queen B can attack 3 other queens and the other queens can attack only 2 or 1 queen. Queen B is "hot". What do we call a Local Search that focuses on first selecting neighborhood moves that change queen B (because queen B impacts more hard/soft constraints than other queens)?

asked 15 Sep '17, 11:58

Geoffrey%20De%20Smet's gravatar image

Geoffrey De ... ♦
3.6k42765
accept rate: 6%

I recall seeing this being called Guided Local Search, but Wikipedia's explanation contradicts that.

(18 Sep '17, 10:09) Geoffrey De ... ♦

I intend to call it Indictment Local Search, as it seems to be nameless?

(26 Sep '17, 06:23) Geoffrey De ... ♦

dynamic degree variable selection

link

answered 26 Sep '17, 10:49

Rob%20Pratt's gravatar image

Rob Pratt
1.2k26
accept rate: 28%

Google scholar has nothing on that - might you have a reference so I can check if it's implementing the same approach?

(26 Sep '17, 11:58) Geoffrey De ... ♦

"dynamic degree" "variable selection"

(26 Sep '17, 12:01) Rob Pratt

Thanks for the pointer. The first result, "Experimental evaluation of modern variable selection strategies in constraint satisfaction problems", is a different algorithm.

(02 Oct '17, 10:06) Geoffrey De ... ♦

Indictment Variable Neighborhood Descent iteratively goes through the neighborhoods and applies the first improving move, just like a normal VND, but the neighborhoods select the varaibles with the worst indictment total first.

An indictment of a variable is the total of constraints matching (in part) this variable and that this variable is therefore partially responsible of triggering. For example, in course scheduling, in a lecture conflict (2 lecture of the same teacher at the same time), both lectures get an indictment for the full weight. We use the word indictment because both lectures look guilty as causing the broken constraint, but if we can change one lecture and the constraint match disappears, the other looks innocent despite the indictment.

Indictment Tabu Search / Indictment Simulated Annealing / Indictment Tabu Search use neighborhoods that have a higher probabilistic chance of selecting variables with a worse indictment total. This probalisty density function can be a block distribution, a linear descending distribution, parabolic distribution, beta distributions, ...

link

answered 02 Oct '17, 10:19

Geoffrey%20De%20Smet's gravatar image

Geoffrey De ... ♦
3.6k42765
accept rate: 6%

edited 02 Oct '17, 10:22

Minizinc (constraint programming environment) uses the annotation "occurrence" in the search strategy to dictate selection of "the variable with the largest number of attached constraints". So maybe "occurrence search"? "Impeachment search" might get a whole lot of people in my country excited for new good reason. :-)

link

answered 03 Oct '17, 16:45

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
14.6k513
accept rate: 19%

1

I meant "Indictment" instead of "Impeachment", but we have a saying: that which fills the heart, overflows the mouth.

(04 Oct '17, 03:27) Geoffrey De ... ♦

I go a step further than looking at the number of "attached" (= "matching") constraints. I also take into account the score impact of those constraints by summing it. For example, a lecture that causes a teacher conflict with another lecture for -1hard constraint, a room cost of -300soft and a front loading violation for -70soft constraint, has an indictment total of -1hard/-370soft (and 3 occurrences), so it will be selected after a lecture with an indictment of -2hard/-4soft, even if that one has only 2 occurrences.

(04 Oct '17, 03:33) Geoffrey De ... ♦
1

To most people (including me), "indictment" connotes accusation (usually a formal legal accusation), and I don't get that sense from your example. Also, the fact that you count hard and soft violations separately is not conveyed. Would something like "weighted conflict search" be too generic?

(04 Oct '17, 08:54) Paul Rubin ♦♦

On "indictment connotes accusation": yes, that's the idea. Let me explain: those 2 lectures which conflict (same teacher at same time) are both being accused of triggering a violation of that constraint. And that's correct: together they are responsible for causing that constraint to match and therefore the score impact. Is this reasoning correct?

(05 Oct '17, 05:07) Geoffrey De ... ♦

On "hard and soft violations separately is not conveyed": actually, I go a step further (that was a simplification). In my implementation, a score can have any number of score levels, such as hard, medium and soft (which are 3 levels) or even 7 levels. I don't think it matters much for this algorithm though: regardless if one does score folding (hard * 1000000 + soft which is bad though) or not, that's an orthogonal feature. So it's not in the name. Wdyt?

(05 Oct '17, 05:11) Geoffrey De ... ♦

How about "multidimensional conflict neighborhood reduction" (or "neighborhood multidimensional conflict reduction")? That avoids the question of whether you collapse the dimensions into one or not. Perhaps it's just a personal quirk, but alarms go off in my mind when I see something that strikes me as anthropomorphism, and "indicting" or "accusing" a variable sets off one of those alarms.

(06 Oct '17, 09:35) Paul Rubin ♦♦

multidimensional makes me think of pareto optimization :/ I 'll think about it.

(06 Oct '17, 09:53) Geoffrey De ... ♦
showing 5 of 7 show 2 more comments
Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Tags:

×8

Asked: 15 Sep '17, 11:58

Seen: 867 times

Last updated: 06 Oct '17, 09:53

OR-Exchange! Your site for questions, answers, and announcements about operations research.