Skip to content

v2.40.0

Choose a tag to compare

@rcrida rcrida released this 12 Aug 08:37
· 327 commits to main since this release

XCSP3 instance parsing (ADR-0014)

Xcsp3Parser.parse(Path) reads an XCSP3 instance file directly into a ConstraintSatisfactionProblem (plus an optional objective for COP instances), via org.xcsp:xcsp3-tools's XML/expression parsing and a new callback handler mapping each construct onto jcsp's existing constraint builder API. Covers variable domains, intension, extension (support tables), allDifferent, sum, count/among, element, ordered, lex, cumulative, circuit, binPacking, and single-variable/sum-type minimize/maximize objectives — anything else fails immediately via UnsupportedXcsp3ConstraintException or the underlying library's own error rather than silently returning an under-constrained model.

A <minimize type="sum">/<maximize type="sum"> objective is always built as a genuine LinearObjective — for maximize, by negating the coefficients at construction rather than the result, since only a real LinearObjective makes BranchAndBoundSolver route pruning through LpModelBuilder's LP relaxation (sound for any coefficient/domain sign, unlike a plain lambda).

TreeSolver fix

While testing a single-variable XCSP3 intension constraint, found that TreeSolver never checked its root variable's value against constraints touching only that one variable (e.g. a PredicateConstraint), since NodeConsistency only prunes true UnaryConstraints and the root-assignment stream was missing the isConsistent filter every other recursion step already had. Fixed, with a regression test. Assignment gains isConsistentAmong, letting this fix (and similar callers) check against a pre-filtered constraint subset instead of rescanning the whole constraint list per candidate value.

Nogood learning generalization

SumBoundConstraint, SumVariableConstraint, LinearBoundConstraint, LinearVariableConstraint, ProductConstraint, and NaryTuplesConstraint now try RangeNogoodConstraint.fromCurrentBounds before falling back to a ground reason, so a learned nogood can cite a variable's whole current bounding interval instead of requiring every variable to already be singleton.

CSPLib coverage

  • Prob001CarSequencingTest — Car Sequencing, exercising globalCardinalityConstraint, elementConstraint, and atMostNConstraint together for the first time
  • New linearBooleanConstraint (LinearBooleanBoundConstraint/LinearBooleanVariableConstraint) — a weighted-sum primitive over Variable<Boolean> terms (e.g. reified indicators), needed because linearConstraint's Map<Variable<N>, N> can't accept a Variable<Boolean> key
  • Prob049NumberPartitioningTest — Number Partitioning via disjointConstraint plus the new linearBooleanConstraint, cross-checked against brute-force enumeration

Benchmarking

New JMH suite (CsplibBenchmarks, in-tree per ADR-0013) covering all 14 CSPLib problems end-to-end, complementing NogoodPropagationBenchmark's narrower CDCL focus.

Domain hierarchy cleanup

  • SetDomain renamed to DiscreteSetDomain — the old name collided with the unrelated set-CP family (SetBoundedDomain, SetIntervalDomain, etc.)
  • ObjectSetDomain/ObjectSingletonDomain/ObjectEmptyDomain now share one hand-written DiscreteDomain.DiscreteDomainBuilder<T> instead of duplicating Lombok-builder collapsing logic
  • SetIntervalDomain's cardinality range now prints as [min..max], consistent with IntRangeDomain

Dependencies

  • Bumped org.jspecify:jspecify from 1.0.0 to 1.0.1

Full changelog: v2.39.0...v2.40.0