DISCROPT is a time-sensitive combinatorial optimizer; it finds the best solution possible within a limited computing budget. These terms need to be clarified.
A (computational) problem has an associated parameter, its size. For example, here's a problem: given a map of 100 cities find a tour that visits each city exactly once. Here, 100 is the size of this particular problem. Algorithms and heuristics are methods that find desirable solutions of all sizes. When we talk about a particular problem, we always have in mind all possible instances and sizes.
An optimization problem asks for the ``best'' solution subjected to an objective function. For example: given a map (of any number of cities), find the best tour that visits each city exactly once. The objective function in this case can be the usual Euclidean metric or measure of distance defined by the user. In DISCROPT, ``best'' always means ``minimized''; it attempts to find a solution with the (almost) smallest or minimized objective value.
Combinatorial means the discrete or finite property of the problem. This means each solution to the problem must be made up in a certain manner by a countable, finite number of ``elements''. In the above examples, a solution is a tour or an ordering of all cities. The elements are cities. Further, a solution (i.e a tour) can be represented as a circular permutation. We observe that many optimization problems can be represented by either ``permutations'', ``subsets'', or ``set partitions''. Hence, these representations together with their slight variants are currently supported.
A user must know and specify which combinatorial representation implied by his optimization problem in order to use DISCROPT. A user only needs to provide an objective function which takes as input an already-defined solution representation and provides its objective value. When DISCROPT is run, it uses already-defined search heuristics to find the best solution within a specified running time. To be flexible and efficient, users are given the options of defining additional functions that altogether serve as an objective function in a local search framework.
Interestingly, running time is a user input. DISCROPT uses its search strategies to find the most minimized solution within this specified running time. This distinct time-sensitive feature is born out of our observation that an abstract optimization problem might have applications with drastically different computing budgets. In one case, a user simply demands for the best possible solution. In others, perhaps more realistic considering the (NP-)hardness of most optimization problems, one can only hope for the best possible within his computing budget.
In the following sections, we will describe by example the process of implementing an optimization problem, a search heuristic, and a solution representation.