'All Different' and 'Is Integer' constraint in Optimization

Amit (view profile)

on 5 Nov 2012
Sub Question 1 -
In Matlab's optimization toolbox or as a third-party Matlab implementation, is there an in-built 'all different' constraint? By 'all different', I mean that an a constraint on a vector to have all values different from each other.
For reference: 'Excel solver' recently included it.
Details on alldifferent constraint can be understood here - http://www.andrew.cmu.edu/user/vanhoeve/papers/alldiff.pdf
Sub Question 2 - Same query for 'is integer' constraint, i.e. the vector elements are constraint to be integers.
Thanks.

Products

Answer by Alan Weiss

Alan Weiss (view profile)

on 5 Nov 2012

If you have continuous variables, then I think the "all different" restriction does not make sense. You can perturb an element by a very small amount and end up with a "different" value, but one which does not really change the value of an objective or constraint function, to within numerical tolerances.
As far as integer constraints, the Optimization Toolbox does not handle such constraints except for the bintprog function. The Global Optimization Toolbox ga function does handle integer constraints, and I believe that you could write a nonlinear constraint function that would attempt to enforce "all different" members of a population. For example, if components 1 through 6 are integer-valued, you could make a nonlinear inequality constraint function that is negative if these 6 elements have different values, and is positive if they have an identical value. For example:
function [c,ceq] = checkdifferent(x)
ceq = [];
ll = length(unique(x(1:6)));
c = -ll + 5.5; % negative when first 6 entries are different
Be warned, I have not tested this to see how well it works in practice.
Alan Weiss
MATLAB mathematical toolbox documentation

Amit

Amit (view profile)

on 6 Nov 2012
Hi Alan, Thanks. Agreed that "all different" constraint would make sense only in case when variables are discrete. So the hirarchy of constraints required would be: Level 1: Is Integer Sub-level 1: All different.
Though I am looking to have a more sounder methodology to enforce all different, because if I embed what you suggest in the overall model to be fitted, it may interfere with the optimization scheme at hand.
Is there anything which, by the nature of it, fundamentally imposes an "all different integers" constraint on a vector?
Thanks.
Alan Weiss

Alan Weiss (view profile)

on 6 Nov 2012
I am not aware of something that "fundamentally imposes an "all different integers" constraint." The nonlinear constraint function I suggested might be worth trying.
Alan Weiss
MATLAB mathematical toolbox documentation