Computing relaxations for the three-dimensional stable matching problem with cyclic preferences

Area of Science:

• Constraint Programming
• Combinatorial Optimization
• Stable Matching Problems

Background:

• Constraint programming effectively solves the three-dimensional stable matching problem with cyclic preferences (3dsm-cyc).
• Current methods only declare unsatisfiable instances as impossible, lacking information on how to resolve them.

Purpose of the Study:

• To adapt existing 3dsm-cyc constraint models for maximum relaxation.
• To compute the smallest modification needed for satisfiability in 3dsm-cyc instances.
• To incorporate costs and find minimum-cost relaxations.

Main Methods:

• Developing four distinct relaxation strategies for 3dsm-cyc constraint models.
• Extending models to handle element costs and identify lowest-cost relaxations.
• Empirical evaluation of the efficiency and overhead of the proposed relaxation models.

Main Results:

• Successfully adapted constraint models for the maximum relaxation of 3dsm-cyc instances.
• Implemented cost-aware relaxation, enabling the selection of minimum-cost solutions.
• Demonstrated that relaxation models exhibit minimal overhead compared to satisfaction-only models.

Conclusions:

• The proposed relaxation models provide valuable insights into unsatisfiable 3dsm-cyc instances.
• These methods efficiently compute minimal modifications and lowest-cost relaxations.
• The approach offers a practical extension to existing constraint programming techniques for stable matching problems.