Existing approaches to identify multiple solutions to combinatorial problems in practice are at best limited in their ability to simultaneously incorporate both diversity among generated solutions and problem-specific desires that may only be discovered or articulated by the user after further analysis of solver output. We propose a general framework for problems of a combinatorial nature that can generate a set of of multiple (near-)optimal, diverse solutions that are further infused with desirable features. We call our approach solution engineering. A key novelty is that desirable solution properties need not be explicitly modeled in advance. We customize the framework to both the mathematical programming and constraint programming technologies, and we subsequently demonstrate its practicality by implementing and then conducting computational experiments on existing test instances from the literature. Our computational results confirm the very real possibility of generating sets of solutions infused with features that might otherwise remain undiscovered.

A wide literature exists on constraint programming model linearization, based on integer domain decomposition. This paper considers the systematic study of classical global constraints, but in the context of mathematical variables. We con- sider constraints originally stated using integer domain variables, for which we investigate new definitions and linear decomposi- tions using bounded rational variables. We introduce a generic scheme for reification and softening. Combined with state-of-the- art decompositions on integer variables, this approach permits solving discrete-continuous high level models using a single modeler, connected to a MILP solver.

Scalability becomes more and more critical to decision support technologies. In order to address this issue in Constraint Programming, we introduce the family of self-decomposable constraints. These constraints can be satisfied by applying their own filtering algorithms on variable subsets only. We introduce a generic framework which dynamically decompose propagation, by filtering over variable subsets. Our experiments over the CUMULATIVE constraint illustrate the practical relevance of self-decomposition.

In this paper we introduce a new cardinality constraint: Ordered Distribute. Given a set of variables, this constraint limits for each value v the number of times v or any value greater than v is taken. It extends the global cardinality constraint, that constrains only the number of times a value v is taken by a set of variables and does not consider at the same time the occurrences of all the values greater than v. We design an algorithm for achieving generalized arc-consistency on ORDERED DISTRIBUTE, with a time complexity linear in the sum of the number of variables and the number of values in the union of their domains. In addition, we give some experiments showing the advantage of this new constraint for problems where values represent levels whose overrunning has to be under control.

Constraint programming techniques are widely used to solve real-world problems. It often happens that such problems are over-constrained and do not have any solution. In such a case, the goal is to find a good compromise. A simple theoretical framework is the Max-CSP, where the goal is to minimize the number of constraint violations. However, in real-life problems, complex rules are generally imposed with respect to violations. Solutions which do not satisfy these rules have no practical interest. Therefore, many frameworks derived from the Max-CSP have been introduced. In this paper, we classify the most usual types of rules, and we show that some of them are not expressible in existing frameworks. We introduce a new paradigm in which all these rules can be encoded, through meta-constraints. Moreover, we show that most of existing frameworks can be included in our model.