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

Constraint programming has proven to be a successful framework for determining whether a given instance of the three-dimensional stable matching problem with cyclic preferences (3dsm-cyc) admits a solution. If such an instance is satisfiable, constraint models can even compute its optimal solution for several different objective functions. On the other hand, the only existing output for unsatisfiable 3dsm-cyc instances is a simple declaration of impossibility. In this paper, we explore four ways to adapt constraint models designed for 3dsm-cyc to the maximum relaxation version of the problem, that is, the computation of the smallest part of an instance whose modification leads to satisfiability. We also extend our models to support the presence of costs on elements in the instance, and to return the relaxation with lowest total cost for each of the four types of relaxation. Empirical results reveal that our relaxation models are efficient, as in most cases, they show little overhead compared to the satisfaction version.

A quest for a fair schedule: The International Young Physicists' Tournament.

The International Young Physicists' Tournament is an established team-oriented scientific competition between high school students from 37 countries on 5 continents. The competition consists of scientific discussions called Fights. Three or four teams participate in each Fight, while rotating the roles of Presenter, Opponent, Reviewer, and Observer among them. The rules of a few countries require that each team announces in advance three problems they will present at the regional tournament. The task of the organizers is to choose the composition of Fights in such a way that each team presents each of its chosen problems exactly once and within a single Fight no problem is presented more than once. Besides formalizing these feasibility conditions, in this paper we formulate several additional fairness criteria for tournament schedules. We show that the fulfillment of some of them can be ensured by constructing suitable edge colorings in bipartite graphs. To find fair schedules, we propose integer linear programs and test them on real as well as randomly generated data.

Neonatal brachial plexus palsy - early diagnosis and treatment.

Background and purpose: The incidence of brachial plexus palsy (BPP) has decreased recently, but the indivi-d-ual's quality of life is endangered. To provide better chan-ces to BPP neonates and infants, the Department of Developmental Neurology worked out, introduced, and applied a complex early therapy, including nerve point stimulation. Methods: After diagnosing the severity of BPP, early intensive and complex therapy should be started. Appro-x-imately after a week or ten days following birth, the slightest form (neurapraxia) normalizes without any intervention, and signs of recovery can be detected around this period. The therapy includes the unipolar nerve point electro-stimulation and the regular application of those elemen-tary sensorimotor patterns, which activate both extremities simultaneously. Results: With the guideline worked out and applied in the Department of Developmental Neurology, full recovery can be achieved in 50% of the patients, and even in the most severe cases (nerve root lesion), functional upper limb usage can be detected with typically developing body-scheme. Conclusion: Immediately starting complex treatment based on early diagnosis alters the outcome of BPP, providing recovery in the majority of cases and enhancing the everyday arm function of those who only partially benefit from the early treatment.

A collection of Constraint Programming models for the three-dimensional stable matching problem with cyclic preferences.

We introduce five constraint models for the 3-dimensional stable matching problem with cyclic preferences and study their relative performances under diverse configurations. While several constraint models have been proposed for variants of the two-dimensional stable matching problem, we are the first to present constraint models for a higher number of dimensions. We show for all five models how to capture two different stability notions, namely weak and strong stability. Additionally, we translate some well-known fairness notions (i.e. sex-equal, minimum regret, egalitarian) into 3-dimensional matchings, and present how to capture them in each model. Our tests cover dozens of problem sizes and four different instance generation methods. We explore two levels of commitment in our models: one where we have an individual variable for each agent (individual commitment), and another one where the determination of a variable involves pairing the three agents at once (group commitment). Our experiments show that the suitability of the commitment depends on the type of stability we are dealing with, and that the choice of the search heuristic can help improve performance. Our experiments not only brought light to the role that learning and restarts can play in solving this kind of problems, but also allowed us to discover that in some cases combining strong and weak stability leads to reduced runtimes for the latter.