Introduction of a new class of variables to discrete and integer programming problems

In formulating a combinatorial optimisation problem (COP) using Discrete or Integer Programming modelling techniques, the modeller is restricted to use only certain pre-defined discrete variables and sets which are linked by sets of linear equality and inequality constraints. Definition of many COPs includes restrictions in which the use of dis-equality (DI) constraints in their mathematical representation is inevitable. To represent this type of constraint a number of binary variables and extra constraints are usually introduced, which lead to an increase in the size of the model in terms of variables and constraints. In this paper, we introduce a new class of discrete variables which enables the modeller to represent DI constraints more efficiently in the mathematical formulation of a combinatorial optimisation problem. We have also introduced a new branching scheme to the conventional simplex based Branch and Bound (B&B) algorithm in order to deal with this type of variables. To study the effect of these variables, we modelled and solved a set of five classic problems, first using conventional MP variables and second, exploiting the new proposed variables, and compared the results. The empirical results show a promising improvement on the performance of the B&B algorithm. The contribution of this paper is (1) the introduction of a new class of discrete variables which can help to build smaller models, and (2) new branching schemes on these variables that can improve the B&B performance.