Linear optimization models describe a set of feasible solutions from a set of inequalities called constraints. Given two models, identifying what is different between those models is a difficult task. For example, an interesting property of these models is that the order of variables and constraints does not change the set of feasible solutions. Therefore, permutations of the variables and constraints result in equal representations of the same model. Furthermore, different components of a linear model can change: variables and constraints (problem matrix), variable and constraint bounds as well as the objective function(s).
The goal of this work is to develop and implement a tool to compare different model representations and to identify and display differences (e.g. added constraints, deleted variables, variable type changes).
- Literature research about suitable methods for determining the equivalence between different representations of the same linear mixed-integer problem.
- Implementation of methods to detect and display a defined set of changes, e.g.
• change of objective function
• added constraints
• added variables
• variable type change
• variable bound change
• constraint bound change
• coefficient change of a constraint
- Validation of the tool on a set of test instances
Model reading is done using Gurobi Optimizer and we will provide demo models for validation.
Skills: Advanced knowledge of linear optimization, analytical thinking, programming
Note: This thesis topic may be written in English or German, as either a Bachelors or Masters thesis.
Contact: Kevin Tierney or Kostja Siefen