Search

Determining whether two STRIPS planning instances are isomorphic is the simplest form of comparison between planning instances. It is also a particular case of the problem concerned with finding an isomorphism between a planning instance P$$ P $$ and a sub‐instance of another instance P′$$ {P}^{\prime } $$. One application of such a mapping is to efficiently produce a compiled form containing all solutions to P$$ P $$ from a compiled form containing all solutions to P′$$ {P}^{\prime } $$. We also introduce the notion of embedding from an instance P$$ P $$ to another instance P′$$ {P}^{\prime } $$, which allows us to deduce that P′$$ {P}^{\prime } $$ has no solution‐plan if P$$ P $$ is unsolvable. In this paper, we study the complexity of these problems. We show that the first is GI‐complete and can thus be solved, in theory, in quasi‐polynomial time. While we prove the remaining problems to be NP‐complete, we propose an algorithm to build an isomorphism when possible. We report extensive experimental trials on benchmark problems that demonstrate conclusively that applying constraint propagation in preprocessing can greatly improve the efficiency of a SAT solver. [ABSTRACT FROM AUTHOR]

Symmetric non-negative matrix factorization (NMF) can naturally capture the embedded clustering structure in the graph representation. It is an important method for linear and nonlinear data clustering applications. However, it is sensitive to the initialization of variables, and the quality of the initialization matrix greatly affects the clustering performance. In semi-supervised clustering, it faces the challenge of learning a more discriminative representation from limited labeled data. This paper introduces a constrained propagation self-adaptive self-supervised non-negative matrix factorization clustering algorithm (CPS³NMF) to solve the above problems. The algorithm propagates finite constraints to unconstrained data points, constructing a similarity matrix imbued with constraint information. The resultant similarity matrix serves the role of a non-negative symmetric matrix decomposition in SNMF and functions as graph regularization for the assignment matrix, fully utilizing the limited constraint information to preserve the geometrical structure of data space. Concurrently, leveraging the sensitivity of initial features in SNMF, the algorithm employs adaptively learned weights to rank the quality of multiple initial matrices. By integrating results from multiple clustering attempts, it progressively enhances the performance of semi-supervised clustering. Experiments on 6 public datasets show that the proposed CPS³NMF algorithm outperforms other state-of-the-art algorithms, proving its effectiveness in semi-supervised clustering. [ABSTRACT FROM AUTHOR]

The Cumulative constraint is a foundamental global constraint, which naturally arises in a variety of problems related to scheduling with limited resources. Since its introduction, numerous propagation algorithms have been proposed, offering different tradeoffs between computational complexity and filtering power. Such diversity allows the resolution of a wide range of applications. Motivated by the impressive computational power that modern Graphical Processing Units (GPUs) provide, this paper explores the use of GPUs for the propagation of the Cumulative constraint. The paper describes the development of a GPU-Acceletated Propagator (GAP), motivates the design choices, and provides solutions for several design challenges. The implementation is evaluated in comparison with state-of-the-art constraint solvers on different benchmarks from the literature. The results suggest that our approach is competitive, providing strong filtering in a reasonable amount of time. [ABSTRACT FROM AUTHOR]

The AllDifferent constraint is a fundamental tool in Constraint Programming. It naturally arises in many problems, from puzzles to scheduling and routing applications. Such popularity has prompted an extensive literature on filtering and propagation for this constraint. This paper investigates the use of General Processing Units (GPUs) to accelerate filtering and propagation. In particular, the paper presents an efficient parallelization of the AllDifferent constraint on GPU, along with an analysis of different design and implementation choices and evaluation of the performance of the resulting system on several benchmarks. [ABSTRACT FROM AUTHOR]

Scheduling frameworks are not necessarily stable. The aim is to introduce schedules resistant to disruptions such as when resources become unavailable, the supply chain for them breaks down, etc. A schedule is robust if it absorbs some level of unforeseen events when at most a certain number of activities are delayed. Taking advantage of constraint programming, we present two new filtering algorithms for a constraint that models cumulative scheduling problems in robust contexts where up to r out of n tasks can be concurrently delayed while keeping the schedule valid. We adapt the overload-checking and edge-finding filtering rules for this framework. We show that our robust versions of these algorithms run in Θ (r 2 n log (n)) and O (r 2 z n log (n)) , respectively, where z denotes the number of distinct capacities of all tasks. This achievement implies that the complexities of the state-of-the-art algorithms for these techniques are invariable when r is constant. Experiments illustrate that our algorithms scale, with respect to n and r. As a practical application, the experimental results on a special case of crane assignment problem also verify a stronger filtering for these methods in terms of backtrack numbers as well as computation times when used in conjunction with time tabling. Finally, in order to show that our CP-based algorithms improve to solve a robust scheduling problem, we make a comparison against temporal protection as an external robust scheduling approach. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms – Discrete. Funding: H. Fahimi received funding from Shahid Chamran University of Ahvaz with [Grant number SCU.MC1402.44132]. C.-G. Quimper was funded by a NSERC Discovery Grant from Canada. Supplemental Material: The e-companion is available at https://doi.org/10.1287/ijoc.2021.0138. [ABSTRACT FROM AUTHOR]

In the era of massive sharing of information, the term social provenance is used to denote the ownership, source or origin of a piece of information which has been propagated through social media. Tracking the provenance of information is becoming increasingly important as social platforms acquire more relevance as source of news. In this scenario, Twitter is considered one of the most important social networks for information sharing and dissemination which can be accelerated through the use of retweets and quotes. However, the Twitter API does not provide a complete tracking of the retweet chains, since only the connection between a retweet and the original post is stored, while all the intermediate connections are lost. This can limit the ability to track the diffusion of information as well as the estimation of the importance of specific users, who can rapidly become influencers, in the news dissemination. This paper proposes an innovative approach for rebuilding the possible chains of retweets and also providing an estimation of the contributions given by each user in the information spread. For this purpose, we define the concept of Provenance Constraint Network and a modified version of the Path Consistency Algorithm. An application of the proposed technique to a real-world dataset is presented at the end of the paper. [ABSTRACT FROM AUTHOR]

Explaining the outcome of programs has become one of the main concerns in AI research. In constraint programming, a user may want the system to explain why a given variable assignment is not feasible or how it came to the conclusion that the problem does not have any solution. One solution to the latter is to return to the user a sequence of simple reasoning steps that lead to inconsistency. Arc consistency is a well-known form of reasoning that can be understood by a human. We consider explanations as sequences of propagation steps of a constraint on a variable (i.e. the ubiquitous revise function in arc-consistency algorithms) that lead to inconsistency. We characterize several cases for which providing a shortest such explanation is easy: For instance when constraints are binary and variables have maximum degree two. However, these polynomial cases are tight. For instance, providing a shortest explanation is NP-hard when constraints are binary and the maximum degree is three, even if the number of variables is bounded. It remains NP-hard on trees, despite the fact that arc consistency is a decision procedure on trees. The problem is not even FPT-approximable unless the FPT ≠ W[2] hypothesis is false. [ABSTRACT FROM AUTHOR]

We study a constraint propagation algorithm to detect infeasibility of a system of linear inequalities over continuous variables, which we call activity propagation. Each iteration of this algorithm chooses a subset of the inequalities and if it infers that some of them are always active (i.e., always hold with equality), it turns them into equalities. We show that this algorithm can be described as chaotic iterations and its fixed points can be characterized by a local consistency, in a similar way to traditional local consistency methods in CSP such as arc consistency. Via complementary slackness, activity propagation can be employed to iteratively improve a dual-feasible solution of large-scale linear programs in a primal-dual loop – a special case of this method is the Virtual Arc Consistency algorithm by Cooper et al. As our second contribution, we show that this method has the same set of fixed points as block-coordinate descent (BCD) applied to the dual linear program. While BCD is popular in large-scale optimization, its fixed points need not be global optima even for convex problems and a succinct characterization of convex problems optimally solvable by BCD remains elusive. Our result may open the way for such a characterization since it allows us to characterize BCD fixed points in terms of local consistencies. [ABSTRACT FROM AUTHOR]

The notion of reparametrizations of Weighted CSPs (WCSPs) (also known as equivalence-preserving transformations of WCSPs) is well-known and finds its use in many algorithms to approximate or bound the optimal WCSP value. In contrast, the concept of super-reparametrizations (which are changes of the weights that keep or increase the WCSP objective for every assignment) was already proposed but never studied in detail. To fill this gap, we present a number of theoretical properties of super-reparametrizations and compare them to those of reparametrizations. Furthermore, we propose a framework for computing upper bounds on the optimal value of the (maximization version of) WCSP using super-reparametrizations. We show that it is in principle possible to employ arbitrary (under some technical conditions) constraint propagation rules to improve the bound. For arc consistency in particular, the method reduces to the known Virtual AC (VAC) algorithm. We implemented the method for singleton arc consistency (SAC) and compared it to other strong local consistencies in WCSPs on a public benchmark. The results show that the bounds obtained from SAC are superior for many instance groups. [ABSTRACT FROM AUTHOR]

A Qualitative Constraint Network (QCN) is a constraint graph representing problems under qualitative temporal or spatial relations. More formally, a QCN includes a set of entities and a list of qualitative constraints defining the possible scenarios between these entities. Qualitative constraints are expressed as disjunctions of binary relations capturing the (incomplete) knowledge between the involved entities. QCNs effectively represent various real-world applications, including scheduling and planning, configuration, and Geographic Information Systems (GIS). It is, however, challenging to elicit, from the user, the QCN representing a given problem. To overcome this difficulty in practice, we propose a new algorithm for learning, through membership queries, a QCN from a non-expert. Membership queries are asked to elicit temporal or spatial relationships between pairs of temporal or spatial entities. To improve the time performance of our learning algorithm, constraint propagation and ordering heuristics are enforced. The goal is to reduce the number of membership queries needed to reach the target QCN. We conducted several experiments on randomly generated temporal and spatial QCN instances to assess the practical effect of constraint propagation and ordering heuristics. The results of the experiments are encouraging and promising. [ABSTRACT FROM AUTHOR]

As a popular data representation technique, Nonnegative matrix factorization (NMF) has been widely applied in edge computing, information retrieval and pattern recognition. Although it can learn parts-based data representations, existing NMF-based algorithms fail to integrate local and global structures of data to steer matrix factorization. Meanwhile, semi-supervised ones ignore the important role of instances from different classes in learning the representation. To solve such an issue, we propose a novel semi-supervised NMF approach via joint graph regularization and constraint propagation for edge computing, called robust constrained nonnegative matrix factorization (RCNMF), which learns robust discriminative representations by leveraging the power of both L2, 1-norm NMF and constraint propagation. Specifically, RCNMF explicitly exploits global and local structures of data to make latent representations of instances involved by the same class closer and those of instances involved by different classes farther. Furthermore, RCNMF introduces the L2, 1-norm cost function for addressing the problems of noise and outliers. Moreover, L2, 1-norm constraints on the factorial matrix are used to ensure the new representation sparse in rows. Finally, we exploit an optimization algorithm to solve the proposed framework. The convergence of such an optimization algorithm has been proven theoretically and empirically. Empirical experiments show that the proposed RCNMF is superior to other state-of-the-art algorithms.

Verification of programs using floating-point arithmetic is challenging on several accounts. One of the difficulties of reasoning about such programs is due to the peculiarities of floating-point arithmetic: rounding errors, infinities, non-numeric objects (NaNs), signed zeroes, denormal numbers, different rounding modes, etc. One possibility to reason about floating-point arithmetic is to model a program computation path by means of a set of ternary constraints of the form and use constraint propagation techniques to infer new information on the variables' possible values. In this setting, we define and prove the correctness of algorithms to precisely bound the value of one of the variables x, y or z, starting from the bounds known for the other two. We do this for each of the operations and for each rounding mode defined by the IEEE 754 binary floating-point standard, even in the case the rounding mode in effect is only partially known. This is the first time that such so-called filtering algorithms are defined and their correctness is formally proved. This is an important slab for paving the way to formal verification of programs that use floating-point arithmetics. [ABSTRACT FROM AUTHOR]

This paper focuses on the reheat furnace scheduling problem (RFSP) which is to assign the slabs to the reheat furnace, make the slab sequence for each furnace and determine the feed-in time and the residence time for each slab in order to reduce the unnecessary energy consumption reflected by minimising the objective under consideration. Differing from the traditional scheduling problem, the actual residence time of each slab in RFSP needs to be decided and it is correlated with its neighbour slabs in the reheating sequence of the same furnace. Firstly, the RFSP is formulated as a mixed integer programming model with consideration of the practical production requirements. The strong NP-hardness of the problem motivates us to develop a scatter search (SS) algorithm to solve the problem approximately. The SS algorithm is improved by constraint propagation (CP) for filtering the infeasible solutions in both the generation of the initial solutions and the improvement procedure. To verify the algorithm performance, the proposed algorithm is compared with ILOG CP Optimiser for small-scaled problems and the standard SS, genetic algorithm (GA) for large-scaled practical problems, respectively. The computational results illustrate that the proposed algorithm is relatively effective and efficient. [ABSTRACT FROM PUBLISHER]

Several methods for dynamically adapting the local consistency property applied by a CP solver during search have been put forward in recent and older literature. We propose the classification of such methods in three categories depending on the level of granularity where decisions about which local consistency property to apply are taken: node, variable, and value oriented. We then present a detailed review of existing methods from each category, and evaluate them theoretically according to several criteria. Taking one recent representative method from each class, we then perform an experimental study. Results show that simple variable and value oriented methods are quite efficient when the older dom/ddeg heuristic is used for variable ordering, while a carefully tuned node oriented method does not seem to offer notable improvement compared to standard arc consistency propagation. In contrast, under the more realistic setting of dom/wdeg, the variable and value oriented methods cannot compete with standard propagation, while the node oriented method is very efficient. Finally, we obtain a new adaptive propagation method by integrating the variable and value oriented approaches and adding an amount of randomization The resulting method is simple, competitive, and almost parameter-free. [ABSTRACT FROM AUTHOR]

Semi-supervised clustering algorithms have several limitations: 1) the computation complexity of them is very high, because calculating the similarity distances of pairs of examples is time-consuming; 2) traditional semi-supervised clustering methods have not considered how to make full use of must-link and cannot-link constraints. In the clustering, the contribution of a few pairwise constraints to the clustering performance is very limited, and some may negatively affect the outcome; and 3) these methods are not effective to handle high dimensional data, especially for time series data. Up to now, few work touched semi-supervised clustering on time series data. To efficiently cluster large-scale time series data, we first tackle contract time series clustering to produce the most accurate clustering results under a contracted time. We propose a semi-supervised time series clustering framework (STSC), which integrates a fast similarity measure and a constraint propagation approach. Based on the proposed framework, two valid semi-supervised clustering algorithms including fssK-means and fssDBSCAN are designed. Experiments on 11 datasets show that our proposed method is efficient and effective for clustering large-scale time series data. [ABSTRACT FROM AUTHOR]

Artificial intelligence largely relies on bounds on differences (BoDs) to model binary constraints regarding different dimensions, such as time, space, costs, and calories. Recently, some approaches have extended the BoDs framework in a fuzzy, "noncrisp" direction, considering probabilities or preferences. While previous approaches have mainly aimed at providing an optimal solution to the set of constraints, we propose an innovative class of approaches in which constraint propagation algorithms aim at identifying the "space of solutions" (i.e., the minimal network) with their preferences, and query answering mechanisms are provided to explore the space of solutions as required, for example, in decision support tasks. Aiming at generality, we propose a class of approaches parametrized over user‐defined scales of qualitative preferences (e.g., Low, Medium, High, and Very High), utilizing the resume and extension operations to combine preferences, and considering different formalisms to associate preferences with BoDs. We consider both "general" preferences and a form of layered preferences that we call "pyramid" preferences. The properties of the class of approaches are also analyzed. In particular, we show that, when the resume and extension operations are defined such that they constitute a closed semiring, a more efficient constraint propagation algorithm can be used. Finally, we provide a preliminary implementation of the constraint propagation algorithms. [ABSTRACT FROM AUTHOR]

This paper studies the steelmaking–refining–continuous casting (SRCC) scheduling problem with considering variable electricity price (SRCCSPVEP). SRCC is one of the critical production processes for steel manufacturing and energy intensive. Combining the technical rules used in iron-steel production practice, time-dependent electricity price is considered to reduce the electricity cost and the associate production cost. A decomposition approach is proposed for the SRCCSPVEP. Without considering the electrical factor, the first phase applies the mathematical programming method to determine the relative schedule plan for each cast. In the second phase, we formulate a scheduling problem of all casts subject to resource constraint and time-dependent electricity price. A heuristic algorithm combined with the constraint propagation is developed to solve this scheduling problem. To investigate and measure the performance of the proposed approach, numerous instances are randomly generated according to the collective data from a well-known iron-steel plant in China. Computational results demonstrate that our algorithm is very efficient and effective in providing high-quality scheduling plans, and the electricity cost can be reduced for the iron-steel plant. [ABSTRACT FROM PUBLISHER]

Word embeddings learn a vector representation of words, which can be utilized in a large number of natural language processing applications. Learning these vectors shares the drawback of unsupervised learning: representations are not specialized for semantic tasks. In this work, we propose a full-fledged formulation to effectively learn semantically specialized word vectors (Sem2Vec) by creating shared representations of online lexical sources such as Thesaurus and lexical dictionaries. These shared representations are treated as semantic constraints for learning the word embeddings. Our methodology addresses size limitation and weak informativeness of these lexical sources by employing a bidirectional constraint propagation step. Unlike raw unsupervised embeddings that exhibit low stability and easily subject to changes under randomness, our semantic formulation learns word vectors that are quite stable. An extensive empirical evaluation on the word similarity task comprised of 11 word similarity datasets is provided where our vectors suggest notable performance gains over state of the art competitors. We further demonstrate the merits of our formulation in document text classification task over large collections of documents. [ABSTRACT FROM AUTHOR]

Ensemble Clustering (EC), which seeks to generate a consensus clustering by integrating multiple base clusterings, has attracted increasing attentions. However, traditional EC methods typically have three main limitations: (1) High dimensional data present a huge challenge to ensemble clustering methods. (2) Most EC algorithms can not use prior information, e.g., pairwise constraints, to enhance the clustering performance. (3) Even in existing semi-supervised ensemble clustering methods, prior information is not sufficiently used, e.g., only used in generating base clusterings. To alleviate these problems, we propose Stratified Feature Sampling for Semi-Supervised Ensemble Clustering (SFS3EC). Firstly, we develop a novel stratified feature sampling method, which can cope with high dimensional data, guarantee the diversity of base clusterings, and reduce the risk that some features are not selected at the same time. Secondly, semi-supervised clustering, i.e., constraint propagation, is applied to obtain base clusterings. Finally, we propose to utilize prior information in both the base clustering generating process and the consensus process, which guarantees that prior information is sufficiently used. We conduct a series of experiments on ten real-world data sets to demonstrate the effectiveness of the proposed model.

Verification of C/C++ programs has seen considerable progress in several areas, but not for programs that use these languages’ mathematical libraries. The reason is that all libraries in widespread use come with no guarantees about the computed results. This would seem to prevent any attempt at formal verification of programs that use them: without a specification for the functions, no conclusion can be drawn statically about the behavior of the program. We propose an alternative to surrender. We introduce a pragmatic approach that leverages the fact that most math.h/cmath functions are almost piecewise monotonic: as we discovered through exhaustive testing, they may have glitches, often of very small size and in small numbers. We develop interval refinement techniques for such functions based on a modified dichotomic search, which enable verification via symbolic execution based model checking, abstract interpretation, and test data generation. To the best of our knowledge, our refinement algorithms are the first in the literature to be able to handle non-correctly rounded function implementations, enabling verification in the presence of the most common implementations. We experimentally evaluate our approach on real-world code, showing its ability to detect or rule out anomalous behaviors. [ABSTRACT FROM AUTHOR]

We study the problem of finding the global optimum of a nonlinear real function over an interval box by means of complete search techniques, namely interval branch-and-bound algorithms. Such an algorithm typically generates a tree of boxes from the initial box by alternating branching steps and contraction steps in order to remove non optimal sub-boxes. In this paper, we introduce a new contraction method that is designed to handle the boundary of the initial box where a minimizer may not be a stationary point. This method exploits the first-order optimality conditions and we show that it subsumes the classical monotonicity test based on interval arithmetic. A new branch-and-bound algorithm has been implemented in the interval solver Realpaver. An extensive experimental study based on a set of standard benchmarks is presented. [ABSTRACT FROM AUTHOR]

In this article we address the problem of cooperative pose estimation in a group of unmanned aerial vehicles (UAVs) in a bounded-error context. The UAVs are equipped with cameras to track landmarks, and with a communication and ranging system to cooperate with their neighbors. Measurements are represented by intervals, and constraints are expressed on the robots poses (positions and orientations). Pose domains subpavings are obtained by using set inversion via interval analysis. Each robot of the group first computes a pose domain using only its sensors measurements. Then, through position boxes exchanges, the positions are cooperatively refined by constraint propagation in the group. Results with real robot data are presented, and show that the position accuracy is improved thanks to cooperation. [ABSTRACT FROM AUTHOR]

Physical design is a crucial stage determining the ultimate performance of very‐large‐scale integration design in which the constraint application plays an important role. Unfortunately, the resulting influence and propagation of the constraint is unknown so far and needs to be studied comprehensively. Here, the authors attempt to evaluate the propagation of the constraint in two different optimisation styles, i.e. embed‐physical‐extract (EPE) style and embed‐optimise‐physical‐extract (EOPE) style. The simulation result shows the survivability of constraint in the EPE style retains intact, while it degraded for a large degree in the EOPE style with the best propagation probability of 49.53%. The result gives evidence of how constraint propagates in the physical design of a circuit. [ABSTRACT FROM AUTHOR]

We develop an idea originally proposed by Michel and Van Hentenryck of how to perform bit-vector constraint propagation on the word level. Most operations are propagated in constant time, assuming the bit-vector fits in a machine word. In contrast, bit-vector SMT solvers usually solve bit-vector problems by (ultimately) bit-blasting, that is, mapping the resulting operations to conjunctive normal form clauses, and using SAT technology to solve them. Bit-blasting generates intermediate variables which can be an advantage, as these can be searched on and learnt about. As each approach has advantages, it makes sense to try to combine them. In this paper, we describe an approach to bit-vector solving using word-level propagation with learning. We have designed alternative word-level propagators to Michel and Van Hentenryck's, and evaluated different variants of the approach. We have also experimented with different approaches to learning and back-jumping in the solver. Based on the insights gained, we have built a portfolio solver, Wombit, which essentially extends the STP bit-vector solver. Using machine learning techniques, the solver makes a judicious up-front decision about whether to use word-level propagation or fall back on bit-blasting. [ABSTRACT FROM AUTHOR]

Path-oriented random testing aims at generating a uniformly distributed sequence of test data from a program input domain space to traverse a desired execution path of the program. To this aim, this article proposes a new algorithm to refine a program inputs domain space from invalid subdomains not covering the path. The validity of the subdomains is checked by a constraint propagation method against the path constraints (PCs). The proposed algorithm uses a divide-and-conquer technique to iteratively split the inputs domain into subdomains and each time refutes those subdomains that are inconsistent with the PCs. The remaining shrunken subdomains provide all possible test data covering the desired path. Obviously, the more accurate the input domain is, the more effective test data will result. Experiments show the proposed method outperformed other related methods on a set of classical benchmark programs. [ABSTRACT FROM AUTHOR]

When interval branch and bound solvers are used for solving numerical constraint satisfaction problems, constraint propagation algorithms are commonly used for filtering/contracting the variable domains. However, these algorithms suffer from the locality problem which is related to the reduced scope of local consistencies. In this work we propose a preprocessing and a filtering technique to reduce the locality problem and to enhance the contraction power of constraint propagation algorithms. The preprocessing consists in constructing a directed acyclic graph (DAG) by merging equivalent nodes (or common subexpressions) and identifying subsystems of n-ary sums in the DAG. The filtering technique consists in applying iteratively HC4 and an ad-hoc technique for contracting the subsystems until reaching a fixed point. Experiments show that the new approach outperforms state-of-the-art strategies using a well known set of benchmark instances. [ABSTRACT FROM AUTHOR]

Arc consistency is the most popular filtering technique for solving constraint satisfaction problems. Constraint check plays a central role in establishing arc consistency. In this paper, we propose a method to save constraint checks in maintaining coarse-grained arc consistency during backtracking search for solving the constraint satisfaction problems. We reduce the support searching range by utilizing the information generated by an AC3.1 algorithm at preprocessing step. Compared with the existing maintaining arc consistency (MAC) algorithms, the proposed MAC3be algorithm saves constraint checks without maintaining additional data structures at each search tree node. Our experimental results show that MAC3be saves both constraint checks and CPU time while solving some benchmark problems.

This paper describes the Multimedia Application for Diet Management (MADiMan), a system that supports users in managing their diets while admitting diet transgressions. MADiMan consists of a numerical reasoner that takes into account users’ dietary constraints and automatically adapts the users’ diet, and of a natural language generation (NLG) system that automatically creates textual messages for explaining the results provided by the reasoner with the aim of persuading users to stick to a healthy diet. In the first part of the paper, we introduce the MADiMan system and, in particular, the basic mechanisms related to reasoning, data interpretation and content selection for a numeric data-to-text NLG system. We also discuss a number of factors influencing the design of the textual messages produced. In particular, we describe in detail the design of the sentence-aggregation procedure, which determines the compactness of the final message by applying two aggregation strategies. In the second part of the paper, we present the app that we developed, CheckYourMeal!, and the results of two human-based quantitative evaluations of the NLG module conducted using CheckYourMeal! in a simulation. The first evaluation, conducted with twenty users, ascertained both the perceived usefulness of graphics/text and the appeal, easiness and persuasiveness of the textual messages. The second evaluation, conducted with thirty-nine users, ascertained their persuasive power. The evaluations were based on the analysis of questionnaires and of logged data of users’ behaviour. Both evaluations showed significant results.