Safe Updates
My interests in Component Based Software Engineering (CBSE) is mostly settled in the area of component updates and dynamic evolution of systems. The most approaches just check the suibsititutability of single components. But what to do, if some components you desperately want to use, are not exact substitutes for the old versions? My answer is to search for compatible combinations consisting of the set of available component versions. As this combinatorial optimization problem is provable NP-hard (See my and Andre's article "Safe Component Updates "), you need methods to shrink the search space.
Boolean Optimization
The problem can be modelled as a Boolean Optimization Problem, also known as 0/1-integer programming. In this model the decision variables xi decide, if a certain component version will be installed in the new system. The constraints, given by matrix A configure, which combinations are allowed at all. The matrix A also defines the n-polyhedron of the according linear problem. If there are optimal solutions, so valid assignments to the decision variables xi, they lie on the border of the polyhedron.
My first impression was, that my problem only creates total unimodular matrices. If this would have been the case, the problem could not be NP-hard as for this special problems effective algorithms exist. (Interior Point e.g. would calculate the solution in linear time!). So, either the problem was not NP-hard and the proof was wrong, or there must be an example of a system configuration, which creates a non total unimodular matrix with a determinant of +/-2.
Because of my blockhead seasoned with some missunderstanding of the definition of total unimodularity, I visited a math professor (Prof. Winfried Hostättler) here at the FernUniversität, who helped me finding such a configuration, which was actually pretty simple. (R = {A1, A2, B1}, A1 requires B1 and A2 requires B1!). So my theory is still valid and I can go on with my research.
Local Search
There are different reasons why boolean optimization is not the best choice to solve the given combinatorial problem. Hence I currently work on a variant of a local search algorithm to find best system configurations. Some good references in this area are:
