Related Experiment Video
Updated: Jun 26, 2026
10:09
Operation of the Collaborative Composite Manufacturing (CCM) System
Published on: October 1, 2019
A collection of Constraint Programming models for the three-dimensional stable matching problem with cyclic
Ágnes Cseh1, Guillaume Escamocher2,3, Begüm Genç2,3,4
1Institute of Economics, Centre for Economic and Regional Studies, Budapest, Hungary.
Constraints : an International Journal
|August 15, 2022
Summary
This study introduces five constraint models for the 3-dimensional stable matching problem, capturing weak and strong stability, and fairness notions. Experiments reveal commitment levels and search heuristics impact performance, with combined stability reducing runtimes.
Area of Science:
- Computer Science
- Artificial Intelligence
- Operations Research
Background:
- The stable matching problem is a fundamental concept in matching theory.
- Existing research primarily focuses on two-dimensional matching problems.
- Higher-dimensional stable matching problems present unique computational challenges.
Purpose of the Study:
- To introduce and evaluate five novel constraint models for the 3-dimensional stable matching problem with cyclic preferences.
- To adapt and incorporate notions of weak and strong stability into these models.
- To translate and integrate fairness criteria (sex-equal, minimum regret, egalitarian) into the 3D matching framework.
Main Methods:
- Development of five distinct constraint models for 3D stable matching.
- Implementation of techniques to capture weak and strong stability.
- Adaptation of fairness metrics for 3D matching scenarios.
- Empirical evaluation across diverse problem sizes and instance generation methods.
- Exploration of individual and group commitment levels within the models.
Main Results:
- Demonstrated the effectiveness of the proposed models in capturing stability and fairness.
- Identified that the choice of commitment (individual vs. group) impacts model suitability based on stability type.
- Showcased the influence of search heuristics, learning, and restarts on problem-solving performance.
- Discovered that combining strong and weak stability can decrease runtime for weak stability computations.
Conclusions:
- The developed constraint models offer a robust framework for addressing the 3D stable matching problem.
- Model performance is sensitive to commitment strategies and the selected search heuristics.
- The study highlights the potential of advanced techniques like learning and restarts for complex matching problems.
Related Concept Videos
01:31Alternative Sets of Equilibrium Equations
When analyzing the behavior of structures, engineers often rely on the concept of equilibrium. This refers to the state where all forces and moments acting on a system balance each other, resulting in no net movement or rotation. In many cases, equilibrium can be described by a set of standard equations. However, in some situations, alternative sets of equilibrium equations must be used to describe the system's behavior accurately.
One example of such a situation can be observed in a...
One example of such a situation can be observed in a...
01:26Constraints and Statical Determinacy
In structural engineering, the equilibrium of a system is not only determined by its equations of equilibrium but also with the help of constraints. Constraints refer to restrictions on the motion of a system. The proper combinations of constraints can minimize the total number of constraints needed to maintain a system in mechanical equilibrium. When this happens, the system is said to be statically determinate. For such systems, the unknown reaction supports can be estimated using equilibrium...
01:13Stability of Equilibrium Configuration: Problem Solving
The stability of equilibrium configurations is an important concept in physics, engineering, and other related fields. In simple terms, it refers to the tendency of an object or system to return to its equilibrium position after being disturbed. The stability of an equilibrium configuration can be analyzed by considering the potential energy function of the system and examining its behavior near the equilibrium point.
Problem-solving in the context of the stability of equilibrium configuration...
Problem-solving in the context of the stability of equilibrium configuration...
01:29Mechanistic Models: Compartment Models in Algorithms for Numerical Problem Solving
Mechanistic models play a crucial role in algorithms for numerical problem-solving, particularly in nonlinear mixed effects modeling (NMEM). These models aim to minimize specific objective functions by evaluating various parameter estimates, leading to the development of systematic algorithms. In some cases, linearization techniques approximate the model using linear equations.
In individual population analyses, different algorithms are employed, such as Cauchy's method, which uses a...
In individual population analyses, different algorithms are employed, such as Cauchy's method, which uses a...
01:29Lagrange Multipliers: One Constraint
In constrained optimization, the objective is to maximize or minimize a quantity while satisfying a fixed condition. A standard example is a rectangular pen built against a barn wall using 100 meters of fencing. Because the wall provides one side of the enclosure, only the other three sides require fencing. The problem is to find the dimensions that produce the greatest possible area.Let L represent the length parallel to the wall and W the width perpendicular to it. The area of the pen is A =...
01:28Lagrange Multipliers: Two Constraints
The method of Lagrange multipliers with two constraints is used to optimize a function subject to two independent constraints. In many applications, the objective function represents a quantity to be maximized or minimized, such as cost, area, distance, or energy. The two constraints represent requirements that the solution must satisfy, such as fixed volume, limited resources, or prescribed dimensions.For a function of three variables, each constraint forms a surface in three-dimensional space.