Building chuffed

[odow]

Since this package has Flat-Zinc interface, is the only thing blocking being able to use solvers like Chuffed a Chuffed_jll package for installation?

How are solutions returned? Do we have a parser for that?

https://github.com/chuffed/chuffed

[dourouc05]

You mention the two road-blockers I see: having a compiled Chuffed available, and parsing the output. In theory, you should be able to ask Chuffed to spit out all solutions or just the optimum one (or the first feasible solution if you're only looking for feasibility): https://github.com/chuffed/chuffed/blob/23b9fcee3bb30b11f68d82ef4534040ebae1a8fb/chuffed/core/options.cpp#L231-L268. Parsing the solutions shouldn't be too hard; outputting them is handled here: https://github.com/chuffed/chuffed/blob/master/chuffed/flatzinc/flatzinc.h#L310-L344 and https://github.com/chuffed/chuffed/blob/master/chuffed/flatzinc/flatzinc.cpp#L471-L522.

The important part would be to build the fzn-chuffed binary: https://github.com/chuffed/chuffed/blob/master/chuffed/flatzinc/fzn-chuffed.cpp.

[odow]

Okay. I'll build you the fzn-chuffed binary if you sort the output parsing?

You should be able to take inspiration from AmplNLWriter.jl. It would be cool if ConstraintProgrammingExtensions.jl could provide an CPE.Optimizer that takes any FlatZinc compatible binary.

[dourouc05]

It would be great!

It would be cool if ConstraintProgrammingExtensions.jl could provide an CPE.Optimizer that takes any FlatZinc compatible binary.

Would that mean that all parameters passed to the solvers would be the same, with the same code for parsing the output? I'm not sure that it does make sense, I'll have to dig into this.

[odow]

The parameters can be different. But if there's a standardized output then yes. If the outputs are solver-specific, we'll have to do something different.

[dourouc05]

As far as I know, there is no normalised way to output solutions, each solver is welcome to do its own thing… But we'll have to see how much they diverge in practice.

[odow]

Seems like there is some standard output formats: https://www.minizinc.org/doc-2.4.3/en/fzn-spec.html#solution-output

[odow]

Is there a collection of flat zinc files anywhere?

[dourouc05]

Is there a collection of flat zinc files anywhere?

You have quite a few here: https://github.com/google/or-tools/tree/stable/examples/flatzinc

[odow]

Okay. Great. I just wanted to check that the binary works:

(base) oscar@Oscars-MBP ~ % /Users/oscar/Documents/Code/Yggdrasil/C/Chuffed/products/Chuffed.v0.10.4.x86_64-apple-darwin/bin/fzn-chuffed ~/Downloads/puzzle.fzn
all = array1d(1..10, [1, 0, 0, 0, 9, 0, 1, 0, 2, 1]);
x = 2;

----------

You just need to wait for https://github.com/JuliaRegistries/General/pull/42432 Then something like this should work

using Chuffed_jll

function run_chuffed(filename)
    io = IOBuffer()
    Chuffed_jll.fznchuffed() do exe
        return run(pipeline(`$(exe) $(filename)`; stdout = io))
    end
    seekstart(io)
    return String(take!(io))
end

[odow]

And it works!

julia> run_chuffed("/Users/oscar/downloads/puzzle.fzn")
"all = array1d(1..10, [1, 0, 0, 0, 9, 0, 1, 0, 2, 1]);\nx = 2;\n\n----------\n"

@glebbelov we can now call chuffed from Julia. Binaries for all platforms are available at https://github.com/JuliaBinaryWrappers/Chuffed_jll.jl/releases/tag/Chuffed-v0.10.4%2B0

[dourouc05]

That went blazingly fast!

How are updates for JLL packages handled? I guess the build script must be updated, to change the Git hash and the version name?

Also, for the MOI wrapper, I guess the best would be to have a Chuffed.jl package? I don't know if I should copy the AmplNLWriter model, as the FlatZinc is already included in CPE (just like MOI.FileFormat).

[glebbelov]

Note that FZN files are solver-specific. So, in general cannot run FZN files compiled for one solver with another, except for very common constraints such as int_lin_le etc. For example, one solver might handle cumulative natively, while another solver would require a decomposition.

So, one general way is to export the model in MZN format and run the minizinc executable, which would compile for the given solver and run it. Collections of MZN models are in the Challenges and here: https://github.com/MiniZinc/minizinc-benchmarks. I understand this would require a dependency on MZN.

The handling of output is enough to run the JuMP->FZN models and obtain the variable values. A FZN solver produces standardized "raw" output, namely for all variables marked with "::output_var/array", as noted above.

Also, solver parameters are standardized here: https://www.minizinc.org/doc-2.4.3/en/fzn-spec.html#command-line-interface-and-standard-options, and for the minizinc executable, solvers can be configured for automatic use by config files, see the following section.

If for whatever reasons it's desired to support the MZN output items https://www.minizinc.org/doc-2.5.5/en/spec.html#output-items: MZN compiler translates that into the form specified by the output item using the .ozn file, which is another result of compilation: MZN is compiled into an FZN and a OZN file. Raw FZN output can be converted to high-level output as follows: fzn-chuffed model.fzn | minizinc --input-from-stdin --ozn model.fzn. When using mzn exe, this is handled transparently.

[odow]

How are updates for JLL packages handled? I guess the build script must be updated, to change the Git hash and the version name?

Yes. It's pretty easy once you get the hang of it. It helped having to do all the COIN-OR stuff. But from the outside it's a little impenetrable.

I guess the best would be to have a Chuffed.jl package?

Note that FZN files are solver-specific.

I guess what makes the most sense then is to have a Chuffed.jl package with an optimizer. It can declare which constraint types it natively supports, and @dourouc05's bridges can do the reformulation from user-land into the constraint types that Chuffed understands. Then the flatzinc writer can spit out something for chuffed. The downside is that this is a lot of extra work, and we'd have to repeat for all solvers.

The alternative is that we make MiniZinc available via Yggdrasil. And then have a mzn writer instead of a fzn writer.

What would you prefer @dourouc05?

[dourouc05]

Both paths are clearly acceptable and suffer from roughly equally major drawbacks:

• outputting "fuller" MiniZinc would require to completely overhaul the existing code paths (FlatZinc is much flatter), and parsing the full MiniZinc syntax would be hard to do with the current compiler design (it's mostly ad-hoc code, based on the fact that FlatZinc is made to be easy to parse without ambiguities). However, that would bring a full MiniZinc dependency to use the solvers (just MiniZinc without its IDE is ~ 20 MB of binary code for Windows x64, plus its standard library, ~ 1 MB). It could also prove harder to understand the code, as a lot of the logic would be within MiniZinc and bugs could lie anywhere (including in MiniZinc).
• having more detailed FlatZinc output, which would also require an overhaul of the generating code, but mostly to enable certain parts. This would be equivalent to replicating a lot of MiniZinc's standard library and the parts that each solver overrides (so duplicate work) for the conversions, but with the level of flexibility that MOI brings (MiniZinc has no flexibility in choosing the rewriting of a model, unlike MOI). Replicating the same level of support as MiniZinc will require a lot of work for each individual solver. However, these rewritings could be written as bridges and be useful for other solvers (outside MiniZinc), which is great for composability, and everything would be written in Julia.

In theory, the second option appeals more to me, but both would require a lot of work. In any case, a major feature of FlatZinc (annotations) is not supported at all right now and I don't know to fit it with MOI…

We should also see if, performance-wise, it would not be much better to write a wrapper for each solver in the end, bypassing any file output (from MOI to FlatZinc) and parsing (from FlatZinc to internal data structures). Maybe MiniZinc is so fast when converting constraints that it would still be the best option for performance… (Even though there is no reason that pure Julia code cannot reach the same level of performance.)

[odow]

However, these rewritings could be written as bridges and be useful for other solvers (outside MiniZinc)

Yeah I was imagining that Chuffed would declare the subset of constraints it supported and the bridges would do the heavy lifting.

Let's go the Chuffed.jl route for now. If it turns out to be too difficult we can re-assess. I don't think we should aim to fully replicate all of MiniZinc (that's a large undertaking). Instead, we should just aim for a minimal viable product to validate the idea.

Here's my PR to AmplNLWriter which is a good place to get inspiration: https://github.com/jump-dev/AmplNLWriter.jl/blob/od/moi10/src/AmplNLWriter.jl It's essentially just a wrapper around MOI.FileFormats.NL.Model, in the same way that Chuffed.Optimizer should be a thin wrapper around CPE.FlatZinc.Optimizer.

[glebbelov]

Let's go the Chuffed.jl route for now.

Should be not that hard if it becomes part of a larger CP ecosystem. Would also allow handling CP constructs not available in MZN, like graph objects or interval variables

[odow]

if it becomes part of a larger CP ecosystem

Yeah, "hard" being the need to write an entire CP ecosystem! But I think we have a lot of the infrastructure in-place. We have the flexible standard form, @dourouc05 has been hard at work on the bridges/redefinitions, and we have a good story around binary installation.

It'd be nice to see more unification of the CP and MIP communities. You should be able to write MIP formulation, sprinkle in some constraint programming concepts, and have everything seamlessly work together.

Would also allow handling CP constructs not available in MZN

Yeah. I'm mindful that MiniZinc does things very well. So we shouldn't be competing over the same features and same set of users. We should instead collaborate on things that MiniZinc can't do, or that JuMP is better positioned to do.

like graph objects or interval variables

The interval variable thing is a hard question. I'd appreciate any insight you have. Here's our previous discussion: https://github.com/jump-dev/MathOptInterface.jl/issues/1253. The issue is that everything in MOI is based around the idea that variables are a scalar object. So as soon as you start having structured variables, things fall apart.

[dourouc05]

Now, Chuffed is in a mostly useable state: https://github.com/dourouc05/Chuffed.jl. Registration is pending. I plan to improve code quality and performance in subsequent releases.

I have one issue that puzzles me: sometimes, the FZN executable ends (with return code 0), but doesn't output anything to stdout. I guess this is a timing issue (like Julia stopping listening before the process has flushed its output).

[odow]

but doesn't output anything to stdout. I guess this is a timing issue (like Julia stopping listening before the process has flushed its output).

That sounds like a bug. Presumably it should flush before exiting.