Bonjour à tous,

Je suis en train de travailler sur un problème imliquant un problème de type MILP (mixed integer linear programming), mais je suis débutant dans le domaine.

Le problème est surtout selon moi que je ne sais pas si ce type de problème a un nom, ce qui pourrait m'aider à trouver plus d'infos :

Le but est de minimiser le nombre de valeurs différentes de débits massiques dans des canaux i :  m_i, dont le nombre est de plusieurs centaines.

En entrée (donc déjà calculé) j'ai des valeurs de puissance à évacuer pour chaque canal : Q_i

J'ai dans le cadre de ce problème diverses (nombreuses) contraintes linéaires mais une ne l'est pas (à mon avis) :

|Qi/mi−Qi′/mi′|<10−3 Avec i' prenant la valeur de chaque canal adjacent au canal i.

Donc le but est de trouver un vecteur de débits massiques satisfaisant les contraintes, mais ayant le plus petit nombre possible de valeurs différentes (donc des diamètres de canaux différents), ou autrement dit maximiser le nombre de débits (diamètres) qui ont la même valeur dans ce vecteur.

C'est ici que je vous demande votre aide : ce problème a-t-il un nom (sans prendre en compte de contrainte non linéaire) ? Est-ce qu'il y a une manière connue de formuler ce problème sous la forme MILP ? 

Comment linéariseriez-vous la fameuse contrainte ?

Merci d'avance !

-
Edité par yvesrobert1 28 avril 2018 à 5:24:05

Je ne pense pas que tu puisses l'exprimer comme un problème MILP (mais je manque d'expérience dans ce domaine). Par contre, il existe des algos lorsque tu as des contraintes non-linéaires. En particulier, dans ce papier, ils proposent un algorithme lorsque tu as une contrainte qui peut s'exprimer sous la forme d'un polynôme du second degré, ce qui est ton cas (il suffit de multiplier ta contrainte par m_i*m_i' puis la mettre au carré), enfin je pense. Ce n 'est sans doute pas adapté à ton problème, mais tu y trouveras peut-être l'inspiration. Sinon, il y a plusieurs entrées sur cette page qui pourraient t'intéresser (pex non-linear programming).

Bonjour et merci pour ta réponse. 

Je vais regarder les liens que tu m'a envoyés c'est gentil de ta part.

Je pense cependant qu'il est possible de le formuler comme un MILP puisqu'à priori je recherche une minimisation d'un nombre entier de valeurs différentes pour mes débits. Je continue de chercher, car c'est à la base de mon travail en ce moment et il faut que je réussisse, donc si tu (ou n'importe qui d'autre d'ailleurs) a des idées à ce propos je suis preneur.

Avez-vous une idée du nom d'un problème ayant pour but de minimiser le nombre de valeurs distinctes dans un vecteur ? Cela m'aiderait beaucoup

Mmmmm, je ne sais pas vraiment. Eventuellement, ça pourrait vu comme minimiser un truc de la forme

\(J(\mathbf u) = \sum_{i=1}^n{|u_i|}\)

On appelle ça une norme \(l^1\), si ça peut aider...

Bonjour et merci pour votre réponse.

Ce problème me prend vraiment la tête je ne sais pas trop comment le prendre tout en gardant des valeurs de débit continues. En effet, j'ai réussi à résoudre ce problème en définissant un vecteur de débits, mais c'est clairement une mauvaise idée étant donné que je perd toute garantie d'optimalité...