[Part6 Theory] Circuit Constraint and Optimization in CP

Lim denne kommandoen inn i din terminal:

Passord for å koble til er

Vennligst svar på alle spørsmål. Intern feil {} har ikke gyldig filetternavn. {} veier for mye.

Spørsmål 1: Filtering a Circuit Constaint

Assume the fixing x[6]=7 occurs. Who will remove the value 7 from the domain of x[12] ?

The Sum constraint

The Element constraint

The Alldifferent constraint

The subtour-elimination filtering

Spørsmål 2: Subtour Elimination Filtering

What additional edge will be removed by the subtour-elimination filtering algorithm for the Circuit constraint if the fixing x[6]=7 occurs?

0 -> 12

4 -> 0

8 -> 6

0 -> 4

6 -> 8

12 -> 0

Spørsmål 3: Circuit Filtering

Select all the statements that are true:

Achieving domain consistency for a Circuit constraint is an NP-hard problem.

The subtour-elimination filtering algorithm runs in O(n) time in the worst case, which can be lowered to O(number of new fixed variables).

The consistency test that verifies that there is a unique strongly connected component can be achieved in O(n) time, where n is the number of variables in the scope of the Circuit constraint.

Spørsmål 4: Large Neighborhood Search

Select all the true statements:

Increasing the number of relaxed variables increases the time between two restarts.

A restart in LNS is always caused by reaching the limit on the number of failures.

LNS is a local-search approach where CP can be used to explore the neighborhood.

Increasing the failure limit and the number of relaxed variables augments the time between two restarts.

A restart in LNS can be caused because the restricted problem has been exhaustively explored.

LNS with a relaxation of 5% of randomly selected variables can always prove the optimality if enough restarts are performed.

The first solution with LNS needs to be found by CP.

Frist	Ingen frist
Innleveringsgrense	2 innleveringer hver 1 time(r)

Informasjon