Algorithms and Constraints

• Diophantine Constraints
  An increasing range of problems in Computer Science and Artificial Intelligence may involve deciding satisfiability, or computing one or all solutions of Diophantine constraints. Application areas include data security problems, data flow analysis, linear reachability for timed automata, model checking, unification theory and automated deduction, termination analysis of term-rewriting systems, among others. There cannot exist a general algorithm to decide whether a given system of polynomial equations with integer coefficients (i.e., a Diophantine equation system) has an integer solution (Y.Matiyasevich, 1970).  For linear constraints, the problem is decidable but NP-complete (Karp, 1972).  The problem of finding all solutions of a system of linear constraints over the nonnegative integers - the so-called the Hilbert basis - is at the heart of various algorithms for equational unification (e.g., AC-unification of terms that involve associative-commutative function symbols). This fact has stimulated a lot of work, over the last 30 years, in particular, during the 1990s, for which LIACC researchers made relevant contributions, namely the Slopes Algorithm. Expertise at LIACC is internationally recognized (e.g., [1], [2], [3], [4]), despite a decrease in recent years of our research effort in this area.
  As linear constraints, non-linear constraints play an important role in automated proof systems. In cooperation with Evelyne Contejean and Claude Marché (LRI/Univ. Paris XI), we have also proposed solving methods for non-linear constraints in finite domains based on pseudo-linearization. This approach links the problem to the computation of (minimal) vector addition chains,  which we investigated very actively around 2000. Finding an optimal chain is an NP-complete problem. This work has application to automatic search for termination orderings (e.g., for term-rewriting systems) based on polynomial interpretations (Contejean et al., 2005).

• Computational Geometry
  Algorithmic problems of geometric nature arise in many application domains, such as spatial databases, geographic information systems, computer graphics, image analysis, automated manufacturing, VLSI design, robotics and bio-informatics. Good solutions to these problems are mostly based on a thorough understanding of the geometric properties of the problem and a proper application of algorithmic techniques and data structures (M. de Berg et al, 2nd Ed, 2000).  Research at LIACC in recent years has mainly addressed

• Guarding and Visibility Problems

• Algorithms for Generation of Polygons

Guarding problems (a.k.a, Art Gallery Problems or Watchmen Problems) have been a fundamental research topic in the areas of visibility and  surveillance. A landmark result by Chvátal (1975) asserts that n/3 stationary guards, with 2Pi range unlimited visibility, are always sufficient and occasionally necessary to guard  any n-vertex simple polygon. For orthogonal polygons, Kahn, Klawe and Kleitman (1983) have shown that this worst-case bound is n/4. In both cases, a placement of the guards can be found in O(n log n). In contrast, the problem of finding the minimum number of (vertex) guards for a specific polygon P is a NP-hard, both for arbitrary (Lee and Li, 1986) and orthogonal polygons (Shuchardt and Hecker, 1995). Existing greedy approximation algorithms for the Minimum Vertex Guard Problem (MVG) transform MVG instances into Minimum Set Cover instances, by decomposing polygon P in such a way that each piece of the decomposition is either totally visible or totally invisible from each vertex. This condition guarantees that  the transformation is exact (i.e., preserves solutions) but may render the decompositions too grained and, consequently, the associated minimum set cover problems too complex. 

Research at LIACC - The Minimum Vertex Guard Problem and Variants: Researchers of LIACC and CEOC/U.Aveiro have proposed an anytime method for solving MVG by successive approximations (Tomás et al. 2003,  Tomás et al. 2006). The idea of this approach is to begin with a coarse decomposition of polygon P, which need not satisfy the  above mentioned restriction on pieces, but, nevertheless, may be useful to obtain upper and lower bounds on the optimal value of MVG with less computational effort. The partition is iteratively refined to shorten the approximation interval, which eventually converges to the optimum. Dominance of visibility regions is dynamically exploited for reducing the dimension of the optimization subproblems that must be solved at each iteration, as it helps identify pieces or vertex-guards that are irrelevant or equivalent for MVG. It is also used to devise heuristics for the choice of pieces that will be refined first. Experimental evaluations of the method have been carried out for orthogonal polygons (Fábio Marques, MSc 2004, and Ana Gonçalves, MSc 2007), also for orthogonal- and Pi-floodlights, and various initial partitions.
Future work at LIACC aims at using this method for investigating open conjectures on vertex floodlight problems.
International collaboration in this scope was partially supported by CRUP, through Spanish-Portuguese bi-lateral action "Algorithmic Problems in Illumination, Visibility and Surveillance" (E77/06), coordinated by M.Abellanas (UPM,Madrid) and L.Bajuelos (CEOC/UA), Jan 2006 - Dec 2007.

The generation of geometric objects  has applications to the experimental evaluation and testing of geometric algorithms.  No polynomial time algorithm is known for generating polygons uniformly, so that some generators employ heuristics (Auer and Held, 1996) or restrict to certain classes of polygons, e.g., monotone, convex  (Zhu et al.1996) or star-shaped (Sohler 1999) polygons. Numerous related problems have also been extensively investigated, as the exact counting or enumeration of polyominoes, but remain challenging open problems in computational geometry or combinatorics. A polyomino is an edge-connected set of unit squares on a regular square lattice (grid). Interest in statistics of polyominoes (lattice animals or clusters) and simple polygons goes far beyond recreational mathematics, as they have been widely used in statistical physics for modeling percolation phenomena in nature (e.g., liquid-flow, crystals, self-organising systems), recently found relevant also  to wireless ad hoc and sensor networks (L.Booth et al, 2003).

Research at LIACC - Generation of Orthogonal Polygons: focused on a representative class of orthogonal polygons that were called grid n-ogons, which are n-vertex polyominoes inscribed in a regular square grid having exactly one edge per grid line. Three different methods have been developed at LIACC for generating (random) grid ogons with a predefined number of vertices.  One follows a constraint programming approach and explores the fact that the generation problem may be modeled naturally as a constraint satisfaction problem in finite domains. It potentially offers great control on polygon characteristics, but is computationally too expensive. Although some improvement has been achieved by exploiting symmetry breaking and geometric constraints, this generator hardly scales up. The other two methods are based on two transformations developed at LIACC -- Inflate-Cut and Inflate-Paste -- and shown to be complete, meaning that every grid n-ogon results from a unit square by applying Inflate-Paste (resp., Inflate-Cut) r times, where r=(n-4)/2 is its number of reflex vertices. Inflate-Cut works by cutting rectangles and Inflate-Paste by gluing rectangles in a restricted way (Tomás et al., 2003 and Tomás et al., 2004]). These construction techniques are relevant to sampling (without guaranteeing a uniform distribution) and backtrack-free enumeration of grid ogons. Moreover, the Inflate-Paste construction was introduced as a proof-technique for combinatorial properties of subclasses of grid n-ogons in a joint work by LIACC and CEOC/UA researchers (Bajuelos et al., 2004).

 

• Matching under Preferences

Matching has been a major focus in market design (Niederle et al., 2008). Labor markets are often two-side markets, where each agent on one side has preferences over agents of the other side e.g., the National Resident Matching Program (1952) and College Admissions (Gale and Shapley, 1962) in US. The preference lists may be strictly or partially ordered and complete or incomplete, modeling situations where it is allowed or disallowed to express indifference and inadmissible pairs. Usually, the goal is to produce a stable matching, which informally means that no pair of agents prefer each other to their partners in the match. Over the last fifty years, much attention has been given to the Stable Marriage (SM) problem and variants. Efficient algorithms exploit strong structural properties of these matchings. Nevertheless, it is known that for stable marriage with ties and incomplete lists (SMTI), some problems are hard and hard to approximate (Manlove et al., 2002).
The situations where the markets are one-sided are ubiquitous in real-life also, being the one-sided housing market problem (Shapley and Scarf, 1974) one of the basic models. The markets may be one-sided because the agents form a unique set or the preferences may be expressed on one side only, although there are still two sets of agents. The latter include housing markets and house allocation problems, where most frequently the goal is to find a Pareto optimal matching. Popular matchings and rank-optimal matchings, which received much attention recently (Irving et al., 2004), may be seen as variants of house allocation problems, although for distinct optimality criteria.  In housing markets each active agent owns an indivisible good (called, a house) whereas in house allocation no agent owns a specific house. In the former case, the allocation must be  individually rational, which means that no agent may receive a house inferior to his own one. House allocation  with existing tenants is an hybrid model introduced by Abdulkadiroglu and Sonmez (1999), where some agents own a house and some are newcomers, agents are not ranked and have strict preferences over all houses and each tenant is allowed to keep his current house.

Research at LIACC - The Teachers Recruitment Problem:   A.P.Tomás at LIACC has investigated a new variant of the house allocation problem with existing tenants, in which the agents are strictly ordered by priority and their preference lists may contain ties and be incomplete. This problem was called the Teachers Recruitment problem (PTTR), for its origin was a real-life teachers recruitment problem, that raised great controversy in Portugal in Fall 2004. The main recruitment program in Portugal has a national scope, with more than one hundred thousand applicants but comparatively very few posts. Applicants are strictly ranked and those that have already permanent posts and try to move cannot result unmatched. In the worst case, they may keep their current posts. PTTR can also be seen as a variant of SMTI if each applicant who had already a permanent post is given top rank for his initial post. The matching must be applicant-optimal stable, i.e., a matching that assigns the best post to each applicant and does not violate their relative priorities.

The main results of this work:  Research was triggered by flaws detected in the Portuguese hiring law for state-school teachers (Tomás 2005). Results sent to the Government were taken in a new law. We showed that PTTR is polynomially solvable, both for strict and tied preferences. For strictly ordered preference lists, PTTR has a unique solution and the Gale-Shapley Algorithm (applicant-oriented) may be used to compute it in O(m), where m is the total length of the preference lists. For preference lists with ties, an efficient algorithm was developed for PTTR, based on a reduction of PTTR to a sequence of maximum cardinality bipartite matching problems on reduced subgraphs, combined with an effective propagation of the stability constraints (Tomás  2006).  Extensive simulations indicate that this algorithm scales up efficiently (we acknowledge an initial contribution of Claúdia Carvalho to this experimental evaluation, as part of her final undergraduate project in Computer Science).
Current work : aims at better characterizing the theoretical asymptotic complexity of this algorithm.

• Constraint Solvers for Computer Assisted Learning
  Applications of computers in education as a supplement to regular class or as a primary means of instruction became more and more widespread. Designing course-ware material for e-learning is still quite time-consuming, even when instructors may count on e-learning authoring tools. Improving students' proficiency in mathematics stands at the top of educational priorities in Portugal, as well as in many countries, nowadays.  Drills and practice, together with exposition, are still the main modes of instruction in mathematics.  Nevertheless, very often drills created by online exercise systems lack pedagogical interest, as they tend  to be too hard-wired and just correspond to randomly generated instances of the same problem template. Advances in computer technology and the internet shall therefore be exploited to develop really re-usable and customizable contents. LIACC researchers pursue this goal in the development of innovative applications of declarative languages to web-based learning environments for computer science and mathematics.

Research at LIACC - Tools for Mathematics Learning: research on constraint models and constraint processing in this scope at LIACC has been twofold, with the goals of supporting configuration constraints and designing dedicated symbolic solvers that may produce human-like solutions to the exercises. The released prototype of AGILMAT (web application for Mathematics education) allows different initial settings by a parametrizing the interface, generator and solver through XML configuration files. The user is given the possibility to further refine some of these parameters in order to customize the exercises. AGILMAT implementation integrates different technologies and programming languages. The core system is implemented in a Prolog-based constraint logic programming language for supporting constraints on the exercises and symbolic processing. 
MATINV - Interactive Mathematics for Blind People, is a project funded by the Portuguese Agency for the Dissemination of Science (Ciencia Viva), and whose prime contractor is Atractor, Interactive Mathematics. The work at LIACC concerns the development of tools for the translation of mathematical texts with LaTeX denotations to the special Braille system used for Mathematics in Portugal, Spain and Latin America. Both LaTeX and Braille have context-dependencies that make the translation not straightforward. There is already a Web site where a prototype of the translator can be experimented with, although at present only by team members. The translator is based on a parser for part of LaTeX, together with a Braille generator, both implemented using DCGs in Prolog. There was also work on a graphical editor for text and mathematical expressions producing LaTeX as part of a final year undergraduate project. Future work will address augmenting the coverage of the translator so that LaTeX texts produced by systems like AGILMAT can be automatically converted to Braille.

 

............... this  page is under construction ...............

[Go back]