[Scip] Mixed-integer problems making use of the alldifferent constraint

[Tobias Achterberg]

Hi Nicolas,

during my research on combining CP and MIP I also thought that the alldifferent constraint 
is a good candidate to integrate into a hybrid solver because of its quite strong domain 
propagation capabilities.

However, I never found a practical problem class where the alldifferent constraint on 
integer variables was useful in the modeling. Something like an alldifferent appears, for 
example, in graph coloring and frequency assignment, and you can also model the traveling 
salesman problem with an alldifferent. But in all of those problem classes, the 
alldifferent is modeled by binary variables, mainly because you cannot really link those 
general integer variables to other constraints.

Even toy problems like n-queens are, in my view, better modeled with binary variables 
because the actual ordering of the general integer numbers does not play a role.


So, as a conclusion, my answer is that I never saw a practical problem for which an 
alldifferent on general integer variables is useful for the modeling.



Best,

Tobias


Nicolas BERGER wrote:
> Le Jeu 2 octobre 2008 11:43, Timo Berthold a écrit :
>> Congratulations, you are member number 100 on our scip mailinglist. :-)
>>
>> Cheers, Timo
>>
> 
> Thanks for the welcome !! Let's see if it's really my lucky day... ;-)
> 
> I am a 3rd year PhD student from Nantes, France, under the direction of
> Pr. Laurent Granvilliers and Dr. Frédéric Goualard, in the "Laboratoire
> d'Informatique de Nantes-Atlantique" (LINA). Our research topic (my thesis
> topic) is about mixed-integer constraint satisfaction techniques.
> 
> We are currently looking for constraint satisfaction problems or
> optimization problems which would make use of alldifferent constraints on
> integer variables AND arithmetic constraints on real variables. We
> actually need to evaluate some of our ideas about efficiently relaxing the
> alldifferent constraint in a mixed-integer interval solver (namely
> 'RealPaver').
> 
> We successfully tested our algorithms on pure discrete problems, such as
> the N queens, but we also need to run these algorithms on mixed-integer
> problems. Do you know where we could find some problems of this kind ?
> 
> 
> Regards,
> Nicolas Berger.
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
>> ----------  Weitergeleitete Nachricht  ----------
>>
>> Betreff: New subscription request to list Scip from
>> nicolas.berger at univ-nantes.fr
>> Datum: Donnerstag 02 Oktober 2008
>> Von: scip-owner at zib.de
>> An: scip-owner at zib.de
>>
>> Your authorization is required for a mailing list subscription request
>> approval:
>>
>>     For:  nicolas.berger at univ-nantes.fr
>>     List: scip at zib.de
>>
>> At your convenience, visit:
>>
>>     http://listserv.zib.de/mailman/admindb/scip
>>
>> to process the request.
>>
>> -------------------------------------------------------
>>
> 
> 
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> http://listserv.zib.de/mailman/listinfo/scip