Skip to content

Release v1.0.0

Latest
Latest

Choose a tag to compare

View all tags
@ThomSerg ThomSerg released this 18 Jul 22:04
· 7 commits to master since this release
v1.0.0
98be9c1
This commit was created on GitHub.com and signed with GitHub’s verified signature.
GPG key ID: B5690EEEBB952194
Verified
Learn about vigilant mode.

Release notes

Added

  • A CPMpy Logo #1060
  • IO module with file format readers and writers #842
  • Datasets: PyTorch-compatible dataset class providing single-line access to datastes from the CO community #900 #1037 #1055:
    • XCSP3
    • JSPLib
    • PSPLib rcpsp
    • MIPLib
    • MaxSAT Eval
    • OPB
    • SAT
    • Nurse rostering
  • New Solvers
    • HiGHS open source ILP solver #868
    • SCIP open source Mixed Integer Programming (MIP) and Mixed Integer Nonlinear Programming (MINLP) solver #412 #955 #982
  • New transformations
  • New Globals
    • Multi-dimensional element NDElement #926 #1018
    • FloatSum to still enable floats in objective #957
    • Markov Decision Diagram (MDD) #924
    • Converted multiplication to a global function #850
    • CumulativeOptional, NoOverlapOptional #676
  • MyPy static type checking #864 #867
  • Proper documentation for NumPy compatibility #1051
  • Support Regular global natively for MiniZinc #952
  • Linearize reified variables #855 #860
  • Custom and typed CSEMap object for Common Subexpression Elimination #917
  • Add encoding variables as expressions to CSE #781
  • IIS-based MUS algorithm #880 #971
  • Native MUS computation for Exact #909
  • Multi-instance tuner #757
  • Add verbosity parameter to tuners #771
  • 'subsolvers' filter argument for SolverLookup.supported() #1030
  • Decorator for non-strict variable name checks #839
  • Description class for human-readable metadata in Expression #903
  • Aspirational unit tests #883
  • Instructions on python-cov #937
  • Sudoku variant examples #777
  • Template docstrings #724
  • Dev script to time transformations #853 848febd
  • Dev script to extract release notes #671

Breaking changes

With this v1.0.0 release, a lot has changed to CPMpy's internal workings. Many transformations have been completely rewritten, internal API signatures have changed and datastructures have been replaced by new ones. We split the breaking changes into two groups: changes that affect what and how you can model (with instructions on how to update your code), and changes to CPMpy's internals, which you will only notice if your code uses those internals directly or if you saved models to .pickle files.

Changes to the modeling API — how to update your code

  • Float objectives are now expressed with the new FloatSum global function #957. Float coefficients are no longer allowed inside regular expressions: multiplying a decision variable with a float constant (e.g. 0.5 * x) raises a TypeError, and Model.minimize()/Model.maximize() only accept integer-valued expressions.
    • If you had a float objective: use FloatSum and pass it directly to a solver object's minimize()/maximize() (supported by OR-Tools, Gurobi, CPLEX, SCIP, HiGHS, Z3, MiniZinc and Hexaly): 
      obj = cp.FloatSum([0.5, 1.5], [x, y])        # replaces 0.5*x + 1.5*y
s = cp.SolverLookup.get("ortools", model)    # model contains only the constraints
s.minimize(obj)
s.solve()
print(obj.value())  # read the objective from the FloatSum;
                    # s.objective_value() stays None when the optimum is not integral
      Note that FloatSum is not an Expression: it cannot be nested inside constraints or other expressions.
    • If you had float coefficients in constraints: rescale them to integers (e.g. replace 0.5*x + 1.5*y <= 2 by x + 3*y <= 4).
  • The deprecated lowercase constraint aliases alldifferent(), allequal() and circuit() are removed #905 #1050 (deprecated since 0.9.0). They are no longer exported from the cpmpy namespace and the functions themselves have been removed from cpmpy.expressions.globalconstraints; use the global constraint classes AllDifferent, AllEqual and Circuit instead.
  • Other functions deprecated since the 0.9.x series are removed #1050:
    • BoolVar(), IntVar() and cparray(): use boolvar(), intvar() and cpm_array() instead.
    • Model.deepcopy() and Expression.deepcopy(): use copy.deepcopy() instead.
    • cpmpy.transformations.negation.negated_normal(): use recurse_negation() (or push_down_negation() on the full expression tree) instead.
    • cpmpy.transformations.get_variables.vars_expr(): use get_variables() instead.
    • cpmpy.solvers.utils.get_supported_solvers() and the builtin_solvers list: use SolverLookup.supported() and SolverLookup.get(name) instead.
  • Multiplication is now a global function instead of an operator #850. x * y creates a Multiplication(x, y) global function (still named "mul") and Operator("mul", ...) can no longer be constructed. Modeling with * is unaffected, but code that inspects expressions with isinstance(expr, Operator) no longer matches multiplications; use isinstance(expr, Multiplication) instead.
  • Element only accepts 1-dimensional arrays #926. Indexing a multi-dimensional array now creates the new NDElement global function. Keep indexing with comma-separated indices (Arr[i,j]) or construct NDElement(Arr, [i,j]) directly; code that constructed Element with a flattened index, or that checks isinstance(expr, Element), must be updated accordingly.
  • NDVarArray is no longer an Expression subclass #886. Variable arrays (as returned by intvar(..., shape=...), boolvar(shape=...) and cpm_array()) are now plain numpy.ndarray subclasses. All modeling functionality is unaffected (vectorized operators, .sum(), .min()/.max(), .any()/.all(), .value(), .implies(), indexing), but code that treats an array as an expression must be updated: isinstance(arr, Expression) now returns False, and arr.args, arr.name and arr.is_bool() no longer exist.
  • Expression arguments are read-only tuples #894. expr.args now returns a tuple instead of a list, so it can no longer be modified in place (e.g. expr.args.append(...) or expr.args[0] = ...). Construct a new expression instead, or use expr.update_args(new_args) for an explicit in-place update.
  • Table, ShortTable and NegativeTable require a rectangular table of integers and a flat array argument #895. The table is converted to, and stored as, a two-dimensional integer numpy array; ragged tables and non-integer entries now raise an error. The array argument is no longer flattened: a nested Python list of variables now raises an error (a multi-dimensional NDVarArray is still accepted and reshaped internally); flatten nested lists yourself, e.g. with cpmpy.expressions.utils.flatlist.
  • Minimum and Maximum no longer flatten nested lists #965. Constructing e.g. Minimum([[x,y],[z]]) no longer works (it creates an invalid expression that fails when solving); pass a flat sequence of expressions instead, e.g. Minimum([x,y,z]) or Minimum(arr.flat). Other globals with variable-length argument lists (AllDifferent, AllEqual, Xor, Increasing, ..., as well as cp.min/cp.max/cp.sum on arrays) are unaffected and still flatten their input.
  • Cumulative and NoOverlap no longer store end in their .args when it is not given #830. Code that unpacks .args (e.g. start, dur, end, demand, cap = c.args) must first check len(c.args); when no end was given, the end times are implicitly start + duration.

Changes to CPMpy's internals — only relevant if you use internals directly or saved models to pickle files

Due to the changes below, models saved to a .pickle file with CPMpy < 1.0.0 will no longer load (or will fail when used) in v1.0.0. Pickle files are tied to the CPMpy version that created them: re-run your model-building code under v1.0.0 and save again. For longer-term storage, consider writing models to a solver-independent text format with the new IO module.

  • All Expression arguments are now stored as immutable tuples instead of lists #894, and the has_subexpr() cache is an eagerly-initialised attribute #895.
  • Expressions created by x * y are Multiplication global functions instead of Operator("mul", ...) #850; multi-dimensional indexing creates NDElement instead of a flattened Element #926.
  • Table-like constraints store their table as a 2D numpy array and keep NDVarArray arguments as-is instead of converting them to Python lists #895.
  • Cumulative and NoOverlap store 4 resp. 2 arguments when no end is given, instead of a None placeholder #830.
  • set_description() now stores a Description object in expr._description; the old expr.desc attribute no longer exists #903.
  • The transformations have been largely rewritten in a new, typed pattern:
    • The deprecated decompose_global() and do_decompose() are removed; use decompose_in_tree() #835, which now also accepts custom (positive) decompositions #929 #980 #1006.
    • The csemap= argument of transformations expects the new CSEMap object instead of a plain dict #917.
    • Several transformations gained parameters or dedicated objective-variants (flatten_constraint(..., do_simplify=), decompose_objective, push_down_negation_objective, safen_objective, decompose_linear, linearize_reified_variables, ...); consult the cpmpy.transformations documentation when upgrading code that calls transformations directly.
  • Solver interfaces: the internal _varmap is keyed by variable name instead of by variable object #990, and solver_var() of the SAT-based interfaces (PySAT, Pindakaas) consistently returns Boolean literals only #1017.
  • The deprecated objective_value= parameter of SolverInterface._solve_return() is removed, as is the internal helper cpmpy.transformations.get_variables._uniquify() #1050.

Minor behavior changes, including bug fixes that may affect code relying on the old behavior

  • Expression <op> ndarray now broadcasts correctly #1035. Using a CPMpy expression on the left-hand side of an operator with a numpy array on the right (e.g. x + np.array([1,2,3])) now broadcasts element-wise and returns an array of expressions, just like the mirrored ndarray <op> Expression always did. Code relying on the old (faulty) single-expression result must be updated.
  • value() returns None for partially-assigned global constraints #872. Xor, Cumulative and Circuit now return None from .value() when some of their arguments have no value (consistent with other expressions), instead of raising an error or computing an incorrect result.
  • Variable values are cleared after an unsatisfiable solve #1001. With Exact and Pindakaas, .value() of variables now returns None after an UNSAT solve call, instead of returning stale values from a previous (satisfiable) solve.
  • cp.sum() over a single expression returns that expression itself, instead of wrapping it in a single-argument sum expression.
  • Expression printing has been refactored #893. The exact output of str(expr) / repr(expr) can differ slightly from previous versions; do not rely on the textual form of expressions.

Deprecated

Old names keep working for now (with a DeprecationWarning where applicable), but will be removed in a future release — switch to the new ones:

  • DIMACS tooling moved to the new IO module #842; cpmpy.tools.dimacs is kept as a backward-compatible wrapper around cpmpy.tools.io.dimacs:
    • read_dimacs(fname) is deprecated; use cpmpy.tools.io.load_dimacs(...), which also accepts the DIMACS content as a string or an open file object.
    • write_dimacs(model, fname) moved to cpmpy.tools.io.write_dimacs(model, path). Note that the second parameter was renamed (fname → path) and that the p cnf header line is no longer written by default; pass p_header=True to restore it.
  • XCSP3 loading: cpmpy.tools.xcsp3.read_xcsp3() is deprecated; use cpmpy.tools.io.load_xcsp3(), which accepts a path, string content or an open file object.
  • XCSP3Dataset moved to the new datasets module #900: import it from cpmpy.tools.datasets (it remains re-exported from cpmpy.tools.xcsp3 for backward compatibility).
  • More generally, the new IO module provides cpmpy.tools.io.load() and cpmpy.tools.io.write() as one-stop entry points that automatically select the format (DIMACS, WCNF, OPB, XCSP3, ...) based on the file extension.
  • SolverLookup.solvernames() now emits a DeprecationWarning; use SolverLookup.supported() instead #1050. Similarly, the deprecated _toplevel/nested arguments of decompose_in_tree() and _toplevel/_nbc of no_partial_functions() now emit a DeprecationWarning and are ignored, instead of raising an assertion error.

Widened and extended APIs (non-breaking)

  • solve() now accepts a display=... callback that reports intermediate solutions during optimisation (supported for OR-Tools, Gurobi, GCS, CP Optimizer, HiGHS and Hexaly), like solveAll() already did #561.
  • solve(assumptions=...) accepts any iterable of Boolean literals, not just a list #712.
  • Global constraint and function constructors are formally typed with the new ExprLike/ListLike type aliases and accept any list-like (list, tuple, numpy array, NDVarArray) of expressions or constants, including numpy integers #871 #873 #874 #877.
  • SolverLookup.supported() gained a subsolvers= flag to optionally exclude subsolver names from the list #1030.
  • The parameter tuners can tune over multiple problem instances at once #757 and take a verbose= level #771.
  • Several globals gained a positive-context decomposition (decompose_positive()) for use in linear/SAT contexts #980 #1006, and AllDifferent a linear one (decompose_linear()) #836.
  • For advanced users: Expression.implies(..., simplify=), flatten_constraint(..., do_simplify=) and decompose_in_tree(..., decompose_custom=, decompose_custom_positive=) expose new optional behavior.

Internal improvements

  • Improvements to toplevel safening #1026
  • New pattern for simplify_boolean #959
  • push_down_negation before decompose#916
  • Improved MUS for Gurobi #993 #1016
  • Improved GCC decomposition #1007
  • Save lhs and rhs of reification to CSEMap #1010
  • Reduction technique for MDD #949
  • Use order encoding for inequalities #994
  • Linear decomposition for Table using MDD #945
  • Fast path solver var #995
  • Canonicalize inequalities #996
  • Refactor decompose in typed pattern #929
  • Simple solver_vars improvements #992
  • Canonicalize neq comparison in CSEMap #969
  • Avoid making auxiliary variables in safening #935
  • Loop optimisations #928
  • Refactor push_down_negation #914
  • Make expr._has_subexpr an attribute #895
  • Simplify Circuit and Inverse decompositions #889
  • Refactor safening transformation #875
  • PySAT pb reification optimisation; let PySAT handle conditionals #783
  • Optimize has_subexpr for tables #596
  • Refactor decompose_in_tree #835

Changed

  • Remove very old deprecated code #1050
  • Improve docs for testing a (new) solver #1031
  • Standardize reporting intermediate solutions #561
  • Remove frozendict dependency #1019
  • Varname in varmap instead of variable object #990
  • GCS refresh install docs, sanitise variable names with commas #973 (thanks Ciaran)
  • Update incrementality test #976
  • Convert assumptions to list #712
  • Modernize examples
    • Counterfactual #931
    • CP explanations #943
    • Diverse solutions #944
    • Maximal propagate #953
    • Stepwise explanations #954
    • Use of NoOverlapOptional in flex jobshop example #947
  • Print display in solver interface superclass #921
  • Small docs/solvers update to be more complete #920
  • Modern __init__ files #905
  • linearize doc update #898
  • Use is None ruff warning #904
  • Remove import * from cpmpy/ tests/ and docs/ #890
  • Don't download examples data files during testsuite #899
  • Refactor infix printing in Operator for improved readability #893
  • Seperate GitHub action runners #885
  • Upgrade pindakaas to v0.5.0 & re-enable BVA for CaDiCal #852 #869
  • Upgrade Z3 lower version to v5.0.0 for upstream bugfix #1052
  • Upgrade Pumpkin interface to v0.3.0 #854
  • OR-Tools and Python version bumps #847
  • Remove solver version upper limits #848
  • Convert TestCase to plain pytest classes #818

Fixed

  • Pumpkin InDomain has_subexpr #1057
  • XCSP3 fixes to parser callbacks #1056 #1058
  • Remove 'mul' from supported for CPLEX #1045
  • Throw NotImplementedError for base classes GlobalConstraint and GlobalFunction #1047
  • XCSP3 runner 'verbose' option #962
  • Implication with single bool in lhs #1043
  • NDVarArray vectorized ops to use NumPy broadcasting #1043
  • Decomposition bugs in Regular and MDD #1039
  • Remove trivial wrapping of bool in linearize_constraint #1042
  • Trivial decompose crash with 0 constraints #1041
  • Flattening of wsum remove in-place edits #1040
  • Fix Expr OP NDArr by doing NDArr ROP Expr #1035
  • Solver var consistent return type #1017
  • Enforce version upper limit on HiGHS due to upstream bug #1032
  • Enforce version upper limit on Choco due to upstream bug #1013
  • Missing RC2 depdendencies in setup.py #1028
  • Table subexpression check #1029
  • Mark inconsistent tests as 'flaky' #1024
  • Fix tests and update requires_solver docs #1002
  • Edge case in canonical_comparison #1014
  • Bounds for pow and mod #1012
  • Fix URL PSPLib #1004
  • Read integers with round instead of int for ILP solvers #884
  • Set stale values to None after infeasability (Exact and pindakaas) #1001
  • Upstream criptominisat fix, remove suppression #978
  • Re-export make_assump_model from tools.explain for legacy code #974
  • Edge case in tuner where time limit can become negative #970
  • Use get_or_make_var for end task variables #964
  • Don't store end args when not given for Cumulative and NopOverlap #830
  • MiniZinc time_limit deprecation warning #927
  • Remove duplicate Comparison handling #951
  • Forgotten comma in supported_globals OR-Tools #942
  • Xor simplification in decomposition #908
  • Fix self += pattern #930
  • Warnings in testsuite #919
  • Re-introduce deprecated variable functions #915
  • Resolve duplicate test names #863
  • Update expression test to not randomly fail #865
  • Fix solution values in int2bool #857
  • Skip tests if Pumpkin not supported #856
  • Make tests solver-independent #779
  • test_transf_comp without increasing counters #638
  • Update value checks on Xor, Cumulative and Circuit #872

Full Changelog: v0.10.1...v1.0.0

Assets 2
Loading