| 1. |
|
|
| 2. |
- Beldiceanu, Nicolas, et al.
(författare)
-
Global Constraint Catalogue: Past, Present and Future
- 2007. - 1
-
Ingår i: Constraints. - : Springer Science and Business Media LLC. - 1383-7133 .- 1572-9354. ; 12:1, s. 21-62
-
Tidskriftsartikel (refereegranskat)abstract
- The catalogue of global constraints is reviewed, focusing on the graph-based description of global constraints. A number of possible enhancements are proposed as well as several research paths for the development of the area.
|
|
| 3. |
|
|
| 4. |
- Beldiceanu, Nicolas, et al.
(författare)
-
On the reification of global constraints
- 2013
-
Ingår i: Constraints. - : Springer Science and Business Media LLC. - 1383-7133 .- 1572-9354. ; 18:1, s. 1-6
-
Tidskriftsartikel (refereegranskat)
|
|
| 5. |
- Beldiceanu, Nicolas, et al.
(författare)
-
Reformulation of global constraints based on constraint checkers
- 2005. - 1
-
Ingår i: Constraints. - : Springer Science and Business Media LLC. - 1383-7133 .- 1572-9354. ; 10
-
Tidskriftsartikel (refereegranskat)abstract
- This article deals with global constraints for which the set of solutions can be recognized by an extended finite automaton whose size is bounded by a polynomial in n, where n is the number of variables of the corresponding global constraint. By reducing the automaton to a conjunction of signature and transition constraints we show how to systematically obtain an automaton reformulation. Under some restrictions on the signature and transition constraints, this reformulation maintains arc-consistency. An implementation based on some constraints as well as on the metaprogramming facilities of SICStus Prolog is available. For a restricted class of automata we provide an automaton reformulation for the relaxed case, where the violation cost is the minimum number of variables to unassign in order to get back to a solution.
|
|
| 6. |
|
|
| 7. |
- Beldiceanu, Nicolas, et al.
(författare)
-
Using finite transducers for describing and synthesising structural time-series constraints
- 2015. - 5
-
Ingår i: Constraints. - : Springer. - 1383-7133 .- 1572-9354. ; 21:1, s. 22-40
-
Tidskriftsartikel (refereegranskat)abstract
- We describe a large family of constraints for structural time series by means of function composition. These constraints are on aggregations of features of patterns that occur in a time series, such as the number of its peaks, or the range of its steepest ascent. The patterns and features are usually linked to physical properties of the time series generator, which are important to capture in a constraint model of the system, i.e. a conjunction of constraints that produces similar time series. We formalise the patterns using finite transducers, whose output alphabet corresponds to semantic values that precisely describe the steps for identifying the occurrences of a pattern. Based on that description, we automatically synthesise automata with accumulators, as well as constraint checkers. The description scheme not only unifies the structure of the existing 30 time-series constraints in the Global Constraint Catalogue, but also leads to over 600 new constraints, with more than 100,000 lines of synthesised code.
|
|
| 8. |
|
|
| 9. |
- Dekker, Jip J., et al.
(författare)
-
Auto-tabling for subproblem presolving in MiniZinc
- 2017
-
Ingår i: Constraints. - : Springer Science and Business Media LLC. - 1383-7133 .- 1572-9354. ; 22:4, s. 512-529
-
Tidskriftsartikel (refereegranskat)abstract
- A well-known and powerful constraint model reformulation is to compute the solutions to a model part, say a custom constraint predicate, and tabulate them within an extensional constraint that replaces that model part. Despite the possibility of achieving higher solving performance, this tabling reformulation is often not tried, because it is tedious to perform; further, if successful, it obfuscates the original model. In order to encourage modellers to try tabling, we extend the MiniZinc toolchain to perform the automatic tabling of suitably annotated predicate definitions, without requiring any changes to solvers, thereby eliminating both the tedium and the obfuscation. Our experiments show that automated tabling yields the same tables as manual tabling, and that tabling is beneficial for solvers of several solving technologies.
|
|
| 10. |
- Devriendt, Jo, et al.
(författare)
-
Learn to relax : Integrating 0-1 integer linear programming with pseudo-Boolean conflict-driven search
- 2021
-
Ingår i: Constraints. - : Springer Science and Business Media LLC. - 1383-7133 .- 1572-9354. ; 26:44565, s. 26-55
-
Tidskriftsartikel (refereegranskat)abstract
- Conflict-driven pseudo-Boolean solvers optimize 0-1 integer linear programs by extending the conflict-driven clause learning (CDCL) paradigm from SAT solving. Though pseudo-Boolean solvers have the potential to be exponentially more efficient than CDCL solvers in theory, in practice they can sometimes get hopelessly stuck even when the linear programming (LP) relaxation is infeasible over the reals. Inspired by mixed integer programming (MIP), we address this problem by interleaving incremental LP solving with cut generation within the conflict-driven pseudo-Boolean search. This hybrid approach, which for the first time combines MIP techniques with full-blown conflict analysis operating directly on linear inequalities using the cutting planes method, significantly improves performance on a wide range of benchmarks, approaching a “best-of-both-worlds” scenario between SAT-style conflict-driven search and MIP-style branch-and-cut.
|
|
