Echtzeitsysteme / Echtzeitsysteme/gips

Special transformation for operator `<==>` including a new substitute MILP variable

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

Description

This issue is a follow-up to https://github.com/Echtzeitsysteme/gips/pull/372#issuecomment-4321553227.

> ### 2. Addition of another complex case
>
> If we are able to express another complex case that came up in my specification, that would help me to eliminate two additional variables and two additional constraints from the GIPSL spec.
>
> Consider the following constraint:
> ```
> constraint with mappingA
> context.variables.v == 1 // v is in {0,1}
> <=>
> [
> context.value == 1
> &
> mappings.B->[...]->sum(element.value) == 0 // the sum can have values > 1
> ]
> }
> ```
>
> If we define a substitute variable `s` in {0,1} with
> - `B := s` and ...
> - `A := mappings.B->[...]->sum(element.value)`,
> we can use your replacement of ...
>
> > `A == 0 <-> B == 1`
> > Resolves to: `(1-B) <= A & A <= (1-B) * M`
>
> to represent the term `mappings.B->[...]->sum(element.value)` with `s` in other replacements.
>
> Now we can use ...
>
> > `A == 1 <-> B == 1 (& C == 1 & ...)`
> > Resolves to: `B (+ C + ...) + (1-n) <= A & A <= B (& A <= C & ...)`
>
> in a simplified form:
>
> - `A == 1 <-> B == 1 & C == 1`
> - `B + C - 1 <= A`
> - `A <= B`
> - `A <= C`
> - Fill in terms:
> - `A := v`
> - `B := context.value`
> - `C := s`
>
> This would lead to the following complete set of replacement constraints for the new complex case above:
>
> ```
> // replacement of original <=> operator
> context.value + s - 1 <= v
> v <= context.value
> v <= s
>
> // s == 1 <=> mapping sum == 0
> 1 - mappings.B->[...]->sum(element.value) <= s
> mappings.B->[...]->sum(element.value) <= (1 - s) * M
> ```

Problems identified by @MarkBeB so far:

- There must be a newly introduced variable in Xtext
- This variable should be hidden/invisible for the user
- Naming collisions should be avoided

Contributor guide

No contributing guide indexed for this repository

Research direction

Start with the discussion linked from pull request #372, then trace the Xtext variable representation and the transformation entry point that handles the `<=>` operator. Done means the new substitute MILP variable is introduced invisibly, avoids naming collisions, and produces the listed replacement constraints for this complex case.

Written by the indexing model from the issue text.

Assessment

Tech stack
java
Domain
compilers, devtools
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Quiet
Clarity
Mostly clear
Newbie friendliness
32/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.