The recently-proposed framework of Predict+Optimize tackles optimization problems with parameters that are unknown at solving time, in a supervised learning setting. Prior frameworks consider only the scenario where all unknown parameters are (eventually) revealed simultaneously. In this work, we propose Multi-Stage Predict+Optimize, a novel extension catering to applications where unknown parameters are revealed in sequential stages, with optimization decisions made in between. We further develop three training algorithms for neural networks (NNs) for our framework as proof of concept, both of which handle all mixed integer linear programs. The first baseline algorithm is a natural extension of prior work, training a single NN which makes a single prediction of unknown parameters. The second and third algorithms instead leverage the possibility of updating parameter predictions between stages, and trains one NN per stage. To handle the interdependency between the neural networks, we adopt sequential and parallelized versions of coordinate descent for training. Experimentation on three benchmarks demonstrates the superior learning performance of our methods over classical approaches.

Predict+Optimize is a recently proposed framework which combines machine learning and constrained optimization, tackling optimization problems that contain parameters that are unknown at solving time. The goal is to predict the unknown parameters and use the estimates to solve for an estimated optimal solution to the optimization problem. However, all prior works have focused on the case where unknown parameters appear only in the optimization objective and not the constraints, for the simple reason that if the constraints were not known exactly, the estimated optimal solution might not even be feasible under the true parameters. The contributions of this paper are two-fold. First, we propose a novel and practically relevant framework for the Predict+Optimize setting, but with unknown parameters in both the objective and the constraints. We introduce the notion of a correction function, and an additional penalty term in the loss function, modelling practical scenarios where an estimated optimal solution can be modified into a feasible solution after the true parameters are revealed, but at an additional cost. Second, we propose a corresponding algorithmic approach for our framework, which handles all packing and covering linear programs. Our approach is inspired by the prior work of Mandi and Guns, though with crucial modifications and re-derivations for our very different setting. Experimentation demonstrates the superior empirical performance of our method over classical approaches.

Restart-based Branch-and-Bound Search (BBS) is a standard algorithm for solving Constraint Optimization Problems (COPs). In this paper, we propose an approach to find good partial assignments to jumpstart search at each restart for general COPs, which are identified by comparing different best solutions found in different restart runs. We consider information extracted from historical solutions to evaluate the quality of the partial assignments. Thus the good partial assignments are dynamically updated as the current best solution evolves. Our approach makes restart-based BBS explore different promising sub-search-spaces to find high-quality solutions. Experiments on the MiniZinc benchmark suite show how our approach brings significant improvements to a black-box COP solver equipped with the state of the art search techniques. Our method finds better solutions and proves optimality for more instances.

Consider the setting of constrained optimization, with some parameters unknown at solving time and requiring prediction from relevant features. Predict+Optimize is a recent framework for end-to-end training supervised learning models for such predictions, incorporating information about the optimization problem in the training process in order to yield better predictions in terms of the quality of the predicted solution under the true parameters. Almost all prior works have focused on the special case where the unknowns appear only in the optimization objective and not the constraints. Hu et al. proposed the first adaptation of Predict+Optimize to handle unknowns appearing in constraints, but the framework has somewhat ad-hoc elements, and they provided a training algorithm only for covering and packing linear programs. In this work, we give a new simpler and more powerful framework called Two-Stage Predict+Optimize, which we believe should be the canonical framework for the Predict+Optimize setting. We also give a training algorithm usable for all mixed integer linear programs, vastly generalizing the applicability of the framework. Experimental results demonstrate the superior prediction performance of our training framework over all classical and state-of-the-art methods.

Dominance breaking is a powerful technique in improving the solving efficiency of Constraint Optimization Problems (COPs) by removing provably suboptimal solutions with additional constraints. While dominance breaking is effective in a range of practical problems, it is usually problem specific and requires human insights into problem structures to come up with correct dominance breaking constraints. Recently, a framework is proposed to generate nogood constraints automatically for dominance breaking, which formulates nogood generation as solving auxiliary Constraint Satisfaction Problems (CSPs). However, the framework uses a pattern matching approach to synthesize the auxiliary generation CSPs from the specific forms of objectives and constraints in target COPs, and is only applicable to a limited class of COPs. This paper proposes a novel rewriting system to derive constraints for the auxiliary generation CSPs automatically from COPs with nested function calls, significantly generalizing the original framework. In particular, the rewriting system exploits functional constraints flattened from nested functions in a high-level modeling language. To generate more effective dominance breaking nogoods and derive more relaxed constraints in generation CSPs, we further characterize how to extend the system with rewriting rules exploiting function properties, such as monotonicity, commutativity, and associativity, for specific functional constraints. Experimentation shows significant runtime speedup using the dominance breaking nogoods generated by our proposed method. Studying patterns of generated nogoods also demonstrates that our proposal can reveal dominance relations in the literature and discover new dominance relations on problems with ineffective or no known dominance breaking constraints.

This paper proposes Branch & Learn, a framework for Predict+Optimize to tackle optimization problems containing parameters that are unknown at the time of solving. Given an optimization problem solvable by a recursive algorithm satisfying simple conditions, we show how a corresponding learning algorithm can be constructed directly and methodically from the recursive algorithm. Our framework applies also to iterative algorithms by viewing them as a degenerate form of recursion. Extensive experimentation shows better performance for our proposal over classical and state of the art approaches.

Dominance breaking is shown to be an effective technique to improve the solving speed of Constraint Optimization Problems (COPs). The paper proposes separate techniques to generalize and make more efficient the nogood generation phase of an automated dominance breaking framework by Lee and Zhong's. The first contribution is in giving conditions that allow skipping the checking of non-efficiently checkable constraints and yet still produce sufficient useful nogoods, thus opening up possibilities to apply the technique on COPs that were previously impractical. The second contribution identifies and avoids the generation of dominance breaking nogoods that are both logically and propagation redundant. The nogood generation model is strengthened using the notion of Common Assignment Elimination to avoid generation of nogoods that are subsumed by other nogoods, thus reducing the search space substantially. Extensive experimentation confirms the benefits of the new proposals.

The paper presents the pedagogical innovations and experience of the co-development of three MOOCs on the subject of “Modeling and Solving Discrete Optimization Problems” by two universities. In a nutshell, the MOOCs feature the Fable-Based Learning approach, which is a form of problem-based learning encapsulated in a coherent story plot. Each lecture video begins with an animation that tells a story following a novel. The protagonists of the story encounter a problem requiring technical assistance from the two professors from modern time via a magical tablet granted to them by a fairy god. The new pedagogy aims at increasing learners' motivation and interests as well as situating the learners in a coherent learning context. In addition to scriptwriting, animation production and situating the teaching materials in the story plot, another challenge of the project is the remote distance between the two institutions as well as the need to produce all teaching materials in both (Mandarin) Chinese and English to cater for different geographic learning needs. The MOOCs have been running recurrently on Coursera since 2017. We present learner statistics and feedback, and discuss our experience with and preliminary observations of adopting the online materials in a Flipped Classroom setting.

Exploiting dominance relations in many Constraint Optimization Problems can drastically speed up the solving process in practice. Identification and utilization of dominance relations, however, usually require human expertise. We present a theoretical framework for a useful class of constraint optimization problems to detect dominance automatically and formulate the generation of the associated dominance breaking nogoods as constraint satisfaction. By controlling the length and quantity of the nogoods, our method can generate dominance break- ing nogoods of varying strengths. Experimentation confirms runtime improvements of up to three orders of magnitude against manual methods.

Restarts are an important technique to make search more robust. This paper is concerned with how to maintain and propagate nogoods recorded from restarts efficiently. It builds on reduced nld-nogoods introduced for restarts and increasing nogoods introduced for symmetry breaking. The paper shows that reduced nld-nogoods extracted from a single restart are in fact increasing, which can thus benefit from the efficient propagation algorithm of the incNGs global constraint. We present a lighter weight filtering algorithm for incNGs in the context of restart-based search using dynamic event sets (dynamic subscriptions). We show formally that the lightweight version enforces GAC on each nogood while reducing the number of subscribed decisions. The paper also introduces an efficient approximation to nogood minimization such that all shortened reduced nld-nogoods from the same restart are also increasing and can be propagated with the new filtering algorithm. Experimental results confirm that our lightweight filtering algorithm and approximated nogood minimization successfully trade a slight loss in pruning for considerably better efficiency, and hence compare favorably against existing state-of-the-art techniques.

The pruning power of partial symmetry breaking depends on the given subset of symmetries to break as well as the interactions among symmetry breaking constraints. In the context of Partial Symmetry Breaking During Search (ParSBDS), the search order determines the set of symmetry breaking constraints to add and thus also makes an impact on node and solution pruning. In this paper, we give the first formal characterization of the pruning behavior of ParSBDS and its improved variants. Introducing the notion of Dominance-Completeness (DC-ness), we show that ParSBDS and variants eliminate the symmetry group of the given subset of symmetries if the resultant search tree is DC, and give an example scenario. Unfortunately, building a DC tree is not always possible. We propose two search heuristics with the aim of having more nodes dominated and thus also pruned during search. Extensive experimentation demonstrates how the proposed heuristics and their combination can drastically reduce the solution set size, search space and runtime when compared against the state-of-the-art static and dynamic symmetry breaking methods.

The paper proposes a dynamic method, Recursive SBDS(ReSBDS), for efficient partial symmetry breaking. Wefirst demonstrate how (partial) Symmetry BreakingDuring Search (SBDS) misses important pruning opportunitieswhen given only a subset of symmetries tobreak. The investigation pinpoints the culprit and in turnsuggests rectification. The main idea is to add extra conditionalconstraints during search recursively to prunealso symmetric nodes of some pruned subtrees. Thus,ReSBDS can break extra symmetry compositions, butis carefully designed to break only the ones that areeasy to identify and inexpensive to break. We presenttheorems to guarantee the soundness and terminationof our approach, and compare our method with popularstatic and dynamic methods. When the variable (value)heuristic is static, ReSBDS is also complete in eliminatingall interchangeable variables (values) given only thegenerator symmetries. Extensive experimentations confirmthe efficiency of ReSBDS, when compared againststate of the art methods.

Distributed constraint solving are useful in tackling constrained problems when agents are not allowed to share his/her private information to others and/or gathering all necessary information to solve the problem in a centralized manner is infeasible. With these two limitations, distributed algorithms solve the problem by coordinating agents to negotiate with each other. However, once information is exchanged during negotiation, the private information may be leaked from one agent to another. We propose and design a framework based on Valuation of Possible States (VPS) to evaluate how well a distributed algorithm preserves the totality of all private information onthe entire system when solving distributed constraint optimization problems, by allowing the uses of different aggregators aggregating agents' individual privacy loss. Two classes of aggregators: idempotent aggregators and risk based aggregators are proposed. We further proposed generalized inference rules to infer privacy loss of individual agents. We implement our work on four distributed constraint solving algorithms: Synchronous Branch and Bound (SynchBB), Asynchronous Distributed Constraint Optimization (ADOPT), Branch and Bound ADOPT (BnB-ADOPT), and Distributed Pseudo-tree Optimization Procedure (DPOP). Preliminary experimental evaluations on two benchmarks, Distributed Multi-Event Scheduling Problem (DiMES) and Random Distributed COP, comparing the four algorithms are performed.

In maintaining consistencies, such as GAC*, FDGAC* and weak EDGAC*, for global cost functions, Weighted CSP (WCSP) solvers rely on the projection and extension operations, which entail the computation of the cost functions' minima. Tractability of this minimum computation is essential for efficient execution. Since projections/extensions modify the cost functions, an important issue is tractable projection-safety, concerning whether minimum cost computation remains tractable after projections/extensions. In this paper, we prove that tractable projection-safety is always possible for projections/extensions to/from the nullary cost function (W0), and always impossible for projections/extensions to/from n-ary cost functions for n > = 2. When n = 1, the answer is indefinite. We give a simple negative example, while Lee and Leung's flow-based projection-safe cost functions are also tractable projection-safe. We propose polynomially decomposable cost functions, which are amenable to tractable minimum computation. We further prove that the polynomial decomposability property is unaffected by projections/extensionsto/from unary cost functions. Thus, polynomially decomposable cost functions are tractable projection-safe. We show that the SOFT_AMONG, SOFT_REGULAR, SOFT_GRAMMAR and MAX_WEIGHT/MIN_WEIGHT are polynomially decomposable. They are embedded in a WCSP solver for extensive experiments to confirm the feasibility and efficiency of our proposal.

EagleEye is an integrated GPS-supported educational system for supporting students and teachers respectively in pursuing and facilitating exploratory learning in outdoor fieldtrip activities. This system has four components, including the (1) Location-based Exploratory Resource Authoring Tool, (2) GPS-supported Exploratory Platform, (3) Repository Server, and (4) Teacher Console. A preliminary study, which involved 40 participants (38 students and 2 teachers from a school) adopting EagleEye in an outdoor fieldtrip activity, was carried out to investigate their perceptions of this system. It was found that EagleEye brought desirable fieldtrip experience to the students. The teachers also perceived positively the educational potential of EagleEye for outdoor fieldtrip activities from both technical and pedagogical perspectives.

Lee and Shum consider cost functions that are Polynomially Linear Projection-Safe (PLPS), but whose minimum cost computation is usually NP-hard. They suggest how such cost functions can still be efficiently propagated using relaxed forms of common consistencies. In this paper, we show that conjunctions of PLPS cost functions are still PLPS, and Lee and Shumâs relaxed consistency method is applicable to give better runtime behavior. We further introduce Polynomially Integral Linear Projection-Safe (PILPS) cost functions, a subclass of PLPS cost functions, which have (a) linear formulations with size polynomial to the number of variables and domain sizes, (b) optimal solutions of the linear relaxation always being integral and (c) the last two conditions unaffected by projections/extensions, even though the operations modify the structure of cost functions. We show that conjunctions of PILPS cost functions are PLPS, which still satisfy conditions (a) and (c). Given a standard WCSP consistency α, we give theorems showing that maintaining relaxed α on a conjunction of PILPS cost functions is stronger than maintaining α on the individual cost functions. A useful application of our method is on some PILPS global cost functions, whose minimum cost computations are tractable and yet those for their conjunctions are not. Experiments are conducted to conï¬rm empirically that maintaining relaxed consistencies on the conjoined cost functions is orders of magnitude more efficient, both in runtime and search space reduction, than maintaining the corresponding standard consistencies on the individual cost functions.

Minimax Weighted Constraint Satisfaction Problems (formerly called Quantified Weighted CSPs) are a framework for modeling soft constrained problems with adversarial conditions. In this paper, we study the effects of a value ordering heuristic in solving ultra-weak solutions on top of the alpha beta tree search with constraint propagation. The value ordering heuristic is based on minimax heuristics from adversarial search, which selects values for variables according to the semantic of quantifiers by considering the problem as a two-player zero sum game. In practice, implementing the heuristic requires costs approximations, and we devise three heuristic variants: HUnary, HBinary, and HFullBinary to approximate costs. In particular, we observe that combining these heuristic variants with consistency notions can achieve a better efficiency and a further reduction of search space. We perform experiments on three benchmarks to compare the effects on applying these heuristic variants, and confirm the feasibility and efficiency of our proposal.

Many combinatorial problems deal with preferences and violations, the goal of which is to find solutions with the minimum cost. Weighted constraint satisfaction is a framework for modeling such problems, which consists of a set of cost functions to measure the degree of violation or preferences of different combinations of variable assignments. Typical solution methods for weighted constraint satisfaction problems (WCSPs) are based on branch-and-bound search, which are made practical through the use of powerful consistency techniques such as AC*, FDAC*, EDAC* to deduce hidden cost information and value pruning during search. These techniques, however, are designed to be efficient only on binary and ternary cost functions which are represented in table form. In tackling many real-life problems, high arity (or global) cost functions are required. We investigate efficient representation scheme and algorithms to bring the benefits of the consistency techniques to also high arity cost functions, which are often derived from hard global constraints from classical constraint satisfaction. The literature suggests some global cost functions can be represented as flow networks, and the minimum cost flow algorithm can be used to compute the minimum costs of such networks in polynomial time. We show that naive adoption of this flow-based algorithmic method for global cost functions can result in a stronger form of null-inverse consistency. We further show how the method can be modified to handle cost projections and extensions to maintain generalized versions of AC* and FDAC* for cost functions with more than two variables. Similar generalization for the stronger EDAC* is less straightforward. We reveal the oscillation problem when enforcing EDAC* on cost functions sharing more than one variable. To avoid oscillation, we propose a weak version of EDAC* and generalize it to weak EDGAC* for non-binary cost functions. Using various benchmarks involving the soft variants of hard global constraints ALLDIFFERENT, GCC, SAME, and REGULAR, empirical results demonstrate that our proposal gives improvements of up to an order of magnitude when compared with the traditional constraint optimization approach, both in terms of time and pruning.

Set and multiset variables in constraint programming have typically been represented using subset bounds. However, this is a weak representation that neglects potentially useful information about a set such as its cardinality. For set variables, the length-lex (LL) representation successfully provides information about the length (cardinality) and position in the lexicographic ordering. For multiset variables, where elements can be repeated, we consider richer representations that take into account additional information. We study eight different representations in which we maintain bounds according to one of the eight different orderings: length-(co)lex (LL/LC), variety-(co)lex (VL/VC), length-variety-(co)lex (LVL/LVC), and variety-length-(co)lex (VLL/VLC) orderings. These representations integrate together information about the cardinality, variety (number of distinct elements in the multiset), and position in some total ordering. Theoretical and empirical comparisons of expressiveness and compactness of the eight representations suggest that length-variety-(co)lex (LVL/LVC) and variety-length-(co)lex (VLL/VLC) usually give tighter bounds after constraint propagation. We implement the eight representations and evaluate them against the subset bounds representation with cardinality and variety reasoning. Results demonstrate that they offer significantly better pruning and runtime.

VISOLE (Virtual Interactive Student-Oriented Learning Environment) is a teacher-facilitated constructivist pedagogical approach to empower game-based learning. In combination with scaffolding, situated cognition, reflection, and debriefing, VISOLE aims at providing students with opportunities to acquire subject specific knowledge in a multi-disciplinary fashion and sharpen their higher-order thinking skills for problem solving. Farmtasia is the first online game designed to facilitate the VISOLE approach. We conducted a qualitative case study, in the setting of formal curricular teaching in a secondary school, to look into the course of students' learning in VISOLE. This paper discusses a part of the entire study, focusing on delineating an impeding phenomenon, arbitrary gaming, which emerged in an academic achievement-oriented student's learning process. The findings provided insights into the issue of implementing VISOLE and game-based learning in general in school education.

Soft constraints are functions returning costs, and are essential in modeling over-constrained and optimization problems. We are interested in tackling soft constrained problems with adversarial conditions. Aiming at generalizing the weighted and quantified constraint satisfaction frameworks, a Quantified Weighted Constraint Satisfaction Problem (QWCSP) consists of a set of finite domain variables, a set of soft constraints, and a min or max quantifier associated with each of these variables. We formally define QWCSP, and propose a complete solver which is based on alpha-beta pruning. QWCSPs are useful special cases of QCOP/QCOP+, and can be solved as a QCOP/QCOP+. Restricting our attention to only QWCSPs, we show empirically that our proposed solving techniques can better exploit problem characteristics than those developed for QCOP/QCOP+. Experimental results confirm the feasibility and efficiency of our proposals.

The solving of Weighted CSP (WCSP) with global constraints relies on powerful consistency techniques, but enforcing these consistencies on soft global constraints is not a trivial task. Lee and Leung suggest that a soft global constraint can be used practically if we can find its minimum cost and perform projections/extensions on it in polynomial time, at the same time projections and extensions should not destroy those conditions. However, there are many useful constraints, whose minimum costs cannot be found in polynomial time. In this paper, we propose a special class of soft global constraints which can be modeled as integer linear programs. We show that they are soft linear projection-safe and their minimum cost can be computed by integer programming. By linear relaxation we can avoid the exponential time taken to solve the integer programs, as the approximation of their actual minimum costs can be obtained to serve as a good lower bound in enforcing the approximated consistency notions. While less pruning can be done, our approach allows much more efficient consistency enforcement, and we demonstrate the efficiency of such approaches experimentally.

Weighted Constraint Satisfaction is made practical by powerful consistency techniques, such as AC*, FDAC* and EDAC*, which reduce search space effectively and efficiently during search, but they are designed for only binary and ternary constraints. To allow soft global constraints, usually of high arity, to enjoy the same benefits, Lee and Leung give polynomial time algorithms to enforce generalized AC* (GAC*) and FDAC* (FDGAC*) for projection-safe soft non-binary constraints. Generalizing the stronger EDAC* is less straightforward. In this paper, we first reveal the oscillation problem when enforcing EDAC* on constraints sharing more than one variable. To avoid oscillation, we propose a weak version of EDAC* and generalize it to weak EDGAC* for non-binary constraints. Weak EDGAC* is stronger than FDGAC* and GAC*, but weaker than VAC and soft k-consistency for k > 2. We also show that weak EDGAC* can be enforced in polynomial time for projection-safe constraints. Extensive experimentation confirms the efficiency of our proposal.

VISOLE (Virtual Interactive Student-Oriented Learning Environment) is a teacher-facilitated pedagogical approach to empower game-based learning. In combination with scaffolding, near real-life gaming participation, reflection, and debriefing, VISOLE aims at providing students with opportunities to acquire subject specific knowledge in a multi-disciplinary fashion and sharpen their higher-order thinking skills for problem solving. Farmtasia is the first online game developed based on this approach. We carried out a qualitative case study in Hong Kong for investigating students’ learning process in VISOLE. This paper discuses a part of the entire study, focusing on delineating (1) an impeding phenomenon, unsustainable gaming, which emerged in an “angry” student’s learning process, and (2) how the teacher’s emotional support mitigated this phenomenon. The findings shed light on the enhancement of the current design of VISOLE.

We provide a reformulation of the constraint hierarchies (CHs) framework based on the notion of error indicators. Adapting the generalised view of local consistency in semiring-based constraint satisfaction problems, we define constraint hierarchy k-consistency (CH-k-C) and give a CH-2-C enforcement algorithm. We demonstrate how the CH-2-C algorithm can be seamlessly integrated into the ordinary branch-and-bound algorithm to make it a finite domain (FD) CH solver. Experimentation confirms the efficiency and robustness of our proposed solver prototype. Unlike other FD CH solvers, our proposed method works for both local and global comparators. In addition, our solver can support arbitrary error functions.

Lee and Siu made possible for the first time modeling and reasoning with set variables in weighted constraint satisfaction problems (WCSPs). In addition to an efficient set variable representation scheme, they also defined the notion of set bounds consistency, which is generalized from NC* and AC* for integer variables in WCSPs, and their associated enforcement algorithms. In this paper, we adapt ideas from FDAC and EDAC for integer variables to achieve stronger consistency notions for set variables. The generalization is non-trivial due to the common occurrence of ternary set constraints. Enforcement algorithms for the new consistencies are proposed. Empirical results confirm the feasibility and efficiency of our proposal.

"Human computation" represents a new paradigm of applications that take advantage of people's desire to be entertained and produce useful metadata as a by-product. By creating games with a purpose, human computation has shown promise in solving a variety of problems that computer computation cannot currently resolve completely. Using the ESP game as an example, we propose a metric, called system gain, for evaluating the performance of human computation systems, and also use analysis to study the properties of the ESP game. We argue that human computation systems should be played with a strategy. To this end, we implement an optimal puzzle selection strategy (OPSA) based on our analysis to improve human computation. Using a comprehensive set of simulations, we demonstrate that the proposed OPSA approach can effectively improve the system gain of the ESP game, as long as the number of puzzles in the system is sufficiently large.

In this paper, we propose an analytical model for computing the utility of ESP games, i.e., the throughput rate of appropriate labels for given puzzles. The model targets generalized games, where the number of players, the consensus threshold, and the stopping condition are variable. Via extensive simulations, we show that our model can accurately predict the stopping condition that will yield the optimal utility of an ESP game under a specific setting. A service provider can therefore utilize the model to ensure that the hosted ESP games produce high-quality labels efficiently, given that the number of players willing to invest time and effort in the game is limited.

In this paper, we propose a novel approach called, Reviewers Authority Testing and Evaluation (RATE), to improve the effectiveness of a manuscript review process. In the proposed RATE approach, we define a RATE model to express a manuscript review process mathematically. We then design a RATE algorithm to rank the authority of each reviewer in the RATE model and consequently calculate the quality score for each manuscript. The experimental results demonstrate that the performance of the RATE algorithm is superior to existing approaches. Furthermore, the experiments on testing algorithm's parameter settings also demonstrate that the proposed RATE algorithm behaves effectively and stably.

Bibliographic attributes extraction is an important research topic for digital libraries. In this paper we propose a rule-based method for bibliographic attributes extraction with Layer-upon-Layer Tagging (LLT). The method analyzes bibliographic attributes' appearances and punctuations to perform format and semantic taggings on two defined parsing layers. The method also resolves to specifically constructed lexicons to achieve high accuracy of semantic tagging. In the experimental evaluation on 1,000 reference strings, the accuracy of author tagging reaches to 96.8% and the accuracy of whole reference tagging is 82.9%. The experimental results demonstrate that the proposed LLT method can tag bibliographic attributes in reference strings with high degree of accuracy.

Learning Villages (LV) is an E-learning platform for people's online discussions and frequently citing postings of one another. In this paper, we propose a novel method to rank credit authors in the LV system. We first propose a k-EACM graph to describe the article citation structure in the LV system. And then we build a weighted graph model k-UCM graph to reveal the implicit relationship between authors hidden behind the citations among their articles. Furthermore, we design a graph-based ranking algorithm, the Credit Author Ranking (CAR) algorithm, which can be applied to rank nodes in a graph with negative edges. Finally, we perform experimental evaluations by simulations. The results of evaluations illustrate that the proposed method works pretty well on ranking the credibility of users in the LV system.

A widely adopted approach to solving constraint satisfaction problems combines systematic tree search with various degrees of constraint propagation for pruning the search space. One common technique to improve the execution efficiency is to add redundant constraints, which are constraints logically implied by others in the problem model. However, some redundant constraints are propagation redundant and hence do not contribute additional propagation information to the constraint solver. Redundant constraints arise naturally in the process of redundant modeling where two models of the same problem are connected and combined through channeling constraints. In this paper, we give general theorems for proving propagation redundancy of one constraint with respect to channeling constraints and constraints in the other model. We illustrate, on problems from CSPlib (http://www.csplib.org), how detecting and removing propagation redundant constraints in redundant modeling can speed up search by several order of magnitudes.

VISOLE (Virtual Interactive Student-Oriented Learning Environment) is a new Game-based Situated Learning Paradigm for Web-based teaching and learning, which aims to help students learn from near real-life experiences and social constructions of knowledge. In this paper, we discuss the theoretical foundation, education paradigm, and technological implementation of VISOLE.

Salinity is the relative concentration of salts in water. In a city of southern China, the local water supply company pumps water from a nearby river for potable use. During the winter dry season, the intrusion of sea water raises the salinity of the river to a high level and affects approximately the daily life of 450,000 residents of the city. In this paper, we report the application of constraint programming to optimize the logistical operations of the raw water system so as to satisfy the daily water consumption requirement of the city and to keep the potable salinity below a desirable level for as many days as possible. Our system has already been delivered to the water supply company for deployment.

Nurse rostering problem is one of the most difficult scheduling problems in artificial intelligence and operation research. In general, it consists of cardinality constraints and special pattern constraints that correspond to the given workforce demands, which form a complex problem structure. Many heuristics algorithms have been proposed to solve this particular problem. In this paper, we demonstrate the efficiency of our newly defined GCS/simplex solver, which incorporates simplex method into the GCS framework, on some difficult nurse rostering problem instances. Experimental results show that the GCS/Simplex solver is efficient in solving this kind of scheduling problems in terms of both computation time and number of fails.

Systematic tree search augmented with constraint propagation has been regarded as the de facto standard approach to solve constraint satisfaction problems (CSPs). The property of completeness of tree search is superior to incomplete stochastic local search, although local search approach is more efficient in general. Many heuristics techniques have been developed to improve the efficiency of the tree search approach. We propose a framework for combining and coordinating a complete tree search solver and a different solver in order to produce a complete and efficient CSP solver. Three different instances of the framework have been suggested including combining complete tree search with stochastic search, mathematical programming approach respectively. The experimental results show that this highly integrated hybrid scheme greatly improve the efficiency of constraint solving process in terms of both computation time and number of backtracking.

We provide a reformulation of the constraint hierarchies (CHs) framework based on the notion of error indicators . Adapting the generalized view of local consistency in semiring-based constraint satisfaction problems (SCSPs), we define constraint hierarchy k -consistency (CH- k -C) and give a CH-2-C enforcement algorithm. We demonstrate how the CH-2-C algorithm can be seamlessly integrated into the ordinary branch-and-bound algorithm to make it a finite domain CH solver. Experimentation confirms the efficiency and robustness of our proposed solver prototype. Unlike other finite domain CH solvers, our proposed method works for both local and global comparators. In addition, our solver can support arbitrary error functions. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

In a decision process, when aggregating two values with conflict meaning, sometimes the result should be a tradeoff between the two values. Applicable to many real problems, compensation operators are aggregation operators with such a property. In order to offer more freedom in the selection of suitable compensation operators for various specific application, this paper explores new sorts of compensation operators. First, we introduce the concept of general compensation operators, which form a subclass of general aggregation operators. The two existing kinds of compensation operators, compensatory operators (a special case of uninorm operators) and averaging operators, are subclasses of our general compensation operators. Second, we identify seven new subclasses of the general compensation operators. Third, we construct a new kind of compensation operator, the gray averaging operator, which can include T-norms, T-conorm and averaging operators as its special cases.

Yager et al. (1996) first introduce compensatory operators. This paper further introduces a kind of weighted compensatory operators, and a kind of prioritised compensatory operators. The difference between these similar classes of operators are identified. In addition, the paper introduces the concepts of ordered weighted/prioritised compensatory aggregation.

Constraint satisfaction problems (CSPs) can be used to model problems in a wide variety of application areas, such as time-table scheduling, bandwidth allocation, and car-sequencing. To solve a CSP means finding appropriate values for its set of variables such that all of the specified constraints are satisfied. Almost all CSPs have exponential time complexity and instances of them may require a prohibitively large amount of time to solve. Consequently, much research has been done in developing efficient methods to solve CSPs. In particular, a generic neural network (GENET) model, developed by C.J. Wang and E.P.K. Tsang (1991), has been demonstrated to work extremely well in solving many CSPs, often finding solutions where other methods fail.

Heuristic repair algorithms, a class of local search methods, demonstrate impressive efficiency in solving some large-scale and hard instances of constraint satisfaction problems (CSPs). We draw a surprising connection between heuristic repair techniques and the discrete Lagrange multiplier methods by transforming CSPs into zero-one constrained optimization problems. A Lagrangian-based search scheme LSDL is proposed. We show how GENET, a representative heuristic repair algorithm, can be reconstructed from LSDL. The dual viewpoint of GENET as a heuristic repair method and Lagrange multiplier method allows us to investigate variants of GENET from both perspectives. Benchmarking results confirm that first, our reconstructed GENET has the same fast convergence behavior as other GENET implementations reported in the literature, competing favourably with other state-of-the-art methods on a set of hard graph colouring problems. Second, our best variant, which combines techniques from heuristic repair and Lagrangian methods, is always more efficient than the reconstructed GENET, and can better it by an order of magnitude.

. Hierarchical constraint logic programming (HCLP) extends the expressive power of constraint logic programming (CLP) by allowing both required and nonrequired constraints, making the framework suitable for resolving and relaxing overconstrained problems. Each non-required constraint in HCLP is associated with a strength and constraint strengths are totally ordered. This artificial restriction is incompatible with a sizeable class of real-life problems, in which some constraints cannot be classified as stronger or weaker than one another. Formulating this class of problems in HCLP in an ad hoc fashion would result in some valid solutions being discarded. To cope with this problem, the HCLP framework is enhanced with a theory of partially ordered constraint hierarchy, resulting in PO-HCLP. Another anomaly of HCLP is due to the frequent need to model a complex constraint using a group of primitive constraints, which is a standard practice in the constraint programming community. It is said that the primitive constraints are related. The lack of language facilities in HCLP to enforce the simultaneous satisfaction or relaxation of a group of related primitive constraints would result in nonsensical as well as valid solutions. To resolve this problem, composite constraints are introduced into (PO-)HCLP. The formal syntax and semantics of PO-HCLP are presented and the soundness and completeness of the results established. A prototype of PO-HCLP(R,W S P W) is constructed using CLP(R).

This paper describes the design and implementation of a constraint-based nurse rostering system using a redundant modeling approach. Nurse rostering is defined as the process of generating timetables for specifying the work shifts of nurses over a given period of time. This process is difficult because the human roster planner has to ensure that every rostering decision made complies with a mixture of hard hospital rules and soft nurse preference rules. Moreover, some nurse shift pre-assignments often break the regularity of wanted (or unwanted) shifts and reduce the choices for other unfilled slots. Soft constraints amount to disjunction, which can be modeled as choices in the search space. This approach, although straightforward, incurs overhead in the search of solution. To reduce search time, we propose redundant modeling, an effective way to increase constraint propagation through cooperations among different models for the same problem. Our problem domain involves around 25 to 28 nurses and 11 shift types. Experiments and pilot testing of the system confirm the effectiveness and efficiency of our method.

This paper describes the design and implementation of a nurse rostering system using a redundant modeling approach. Nurse rostering is defined as a process of generating timetables for specifying the work shifts of nurses over a given period of time. This process is difficult because the human roster planner has to ensure that every rostering decision made complies with a mixture of hard hospital rules and soft nurse preference rules. Moreover, some nurse shift pre-assignments often break the regularity of wanted (or unwanted) shifts and reduce the choices for other unfilled slots. Soft constraints amount to disjunction, which can be modeled as choices in the search tree. This approach, although straightforward, incurs overhead in the search of solution. We propose redundant modeling, an effective way to speed up constraint propagation through cooperations among different models for the same problem, as a means to reduce search time. Experiments and pilot testing of the system confirm the feasibility of our method.

GENET has been shown to be efficient and effective on certain hard or large constraint satisfaction problems. Although GENET has been enhanced to handle also the atmost and illegal constraints in addition to binary constraints, it is deficient in handling non binary constraints in general. We present E-GENET, an extended GENET. E-GENET features a convergence and learning procedure similar to that of GENET and a generic representation scheme for general constraints, which range from disjunctive constraints to non linear constraints to symbolic constraints. We have implemented an efficient prototype of E-GENET for single processor machines. Benchmarking results confirms the efficiency and flexibility of E-GENET. Our implementation also compares well against CHIP, PROCLANN, and GENET.

We propose an integration of constraint interval arithmetic into logic programming at the machine architectural level, of which WAM is the de facto standard. The language in consideration is ICL, a subset of ICHIP which shares the same semantic properties as CHIP. We use the work of D. Diaz and P. Codognet (1993) as a starting point, and exploit the simplicity of interval constraint solving over finite domain constraint solving. The resulting extension of WAM Is simple, efficient, robust, and portable. Our ICL prototype compares favourably against BNR Prolog, CLP(BNR), Echidna, and CLP(R) in various types of numerical examples.>

We present a general framework for integrating artificial neural networks (ANN) into constraint logic programming for solving constraint satisfaction problems (CSPs). This framework is realized in a novel programming language PROCLANN, which uses the standard goal reduction strategy as frontend to generate constraints for an efficient backend ANN-based constraint-solver. PROCLANN retains the simple and elegant declarative semantics of constraint logic programming. Its operational semantics is probabilistic in nature but it possesses soundness and completeness results. An initial prototype of PROCLANN is constructed and provides empirical evidence that PROCLANN compares favourably against the state of art in CLP implementations on certain hard instances of CSP.>