Echtzeitsysteme / Echtzeitsysteme/gips

Sorting Matches and Constraints: remaining non-determinism

Open
#319 0 comments 0 reactions 0 assignees View on GitHub
bug
Dominant language
Java
Stars
7
Forks
4
Avg merge
5d 11h
Merged PRs (30d)
10

Description

Standing issues:

- The LHS terms of constraints are not built in a deterministic way; the process that builds them uses `parallelStream` whenever possible. To 'fix' this, we could adjust the code generator so that it uses either `stream` or `parallelStream` depending on a flag in the preferences, or change the code so that we can switch between parallel and serial processing at runtime. (e.g. a boolean flag).
- org.emoflon.gips.build.generator.templates.GipsAPITemplate.generateValueAccess(ValueExpression, boolean)
- org.emoflon.gips.build.generator.templates.ProblemGeneratorTemplate.generateValueAccess(ValueExpression, boolean)
- org.emoflon.gips.build.generator.templates.ProblemGeneratorTemplate.generateAttributeExpression(AttributeExpression)

- The order in which pattern matches are transformed into constraints is possible not deterministic either. The current process involves obtaining a list of matches per pattern via the eMoflon-API. But afaik, matches are added to the list in the order they are discovered, which is not deterministic.
- org.emoflon.gips.core.gt.GipsPatternConstraint.buildConstraints()
- org.emoflon.gips.core.GipsConstraint.calcAdditionalVariables()

- For some reason, running `constraints.values().parallelStream().forEach(constraint -> constraint.calcAdditionalVariables());` in parallel can sometimes affect the order of the constraints' terms in the Gurobi model later on. For example, the linear expression -a + b ≥ 0 may later turn into b − a ≥ 0. I couldn't figure out how to retrieve an expression from the Gurobi model to check at what point this (sometimes) happens. My best guess is that this could be related to the order in which variables are defined in the Gurobi model.
- org.emoflon.gips.core.GipsEngine.buildProblem(boolean, boolean)

_Originally posted by @MarkBeB in https://github.com/Echtzeitsysteme/gips/issues/308#issuecomment-3616084198_

Contributor guide

No contributing guide indexed for this repository

Research direction

Start by tracing the listed generateValueAccess and generateAttributeExpression methods, then read GipsPatternConstraint.buildConstraints, GipsConstraint.calcAdditionalVariables, and GipsEngine.buildProblem. Run repeated builds while comparing constraint and term ordering under serial and parallel processing. Done means repeated runs produce deterministic constraint and term order in the Gurobi model.

Written by the indexing model from the issue text.

Assessment

Tech stack
java
Domain
build-system, tooling
Issue type
Bug
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.