  We propose a multi-criteria Composite Index Method (CIM) to compare the
performance of alternative approaches to solving an optimization problem. The
CIM is convenient in those situations when neither approach dominates the other
when tested on different sizes of problem instances. The CIM takes problem
instance size and multiple performance criteria into consideration within a
weighting scheme to produce a single number that measures the relative
improvement of one alternative over the other. Different weights are given to
each dimension based on their relative importance as determined by the end
user. We summarize the successful application of the CIM to an NP-hard
combinatorial optimization problem known as the backhaul profit maximization
problem (BPMP). Using the CIM we tested a series of eleven techniques for
improving solution time using CPLEX to solve two different BPMP models proposed
in the literature.
