[Part6 Theory] Circuit Constraint and Optimization in CP

עליך להדביק את הפקודה הזאת במסוף שלך:

הסיסמה להתחברות אל

נא לענות על כל השאלות. שגיאה פנימית ל־{} אין סיומת תקפה. {} כבדה מדי.

שאלה 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 Element constraint

The subtour-elimination filtering

The Alldifferent constraint

The Sum constraint

שאלה 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?

4 -> 0

8 -> 6

0 -> 12

6 -> 8

12 -> 0

0 -> 4

שאלה 3: Circuit Filtering

Select all the statements that are true:

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).

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

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.

שאלה 4: Large Neighborhood Search

Select all the true statements:

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

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

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

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

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

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

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

מועד הגשה	אין מועד הגשה
מגבלת הגשות	2 הגשות כל 1 שעות

מידע