Solving combinatorial problems: an XML-based software development infrastructure

Abstract

The resolution of combinatorial problems typically requires the articulation of tools that range from modeling languages to dedicated solvers, including processing input data sets and visualizing results. This work concerns the improvement of the software development environment for a research project using a custom-designed XML dialect. NestingXML has been designed to capture one kind of combinatorial problems in what concerns their input and output data. The dialect is used for storing problem and solution descriptions in a flexible way. In a project context, data formatted according to the dialect are imported into a Java API used for developing solvers and associated tools. The problem description is enriched with both preprocessing data and solution descriptions. We describe the NestingXML dialect and the Java API used in the project and illustrate their use in the problem-solving process. The resulting environment demonstrates increased flexibility in data representations and will become an easy integration medium for new team members.