COIN-OR: Quelles valeurs une variable entière positive bornée prend-elle dans un processus d'optimisation résolu par CBC?

Question

J'essaie de résoudre un problème MILP avec PuLP et CBC. À l'exception du reste du problème, je suis confronté à un problème avec un ensemble de variables entières positives. J'ai une contrainte avec relaxation, ce qui signifie que certaines des variables dans les variables entières positives ne sont pas fixées à une certaine valeur en raison des contraintes. Donc, en reformulant, à partir d'un ensemble de contraintes entières positives, certaines ont des valeurs dues à une contrainte, mais quand cette même contrainte est relâchée (grand M relaxation), le reste des variables n'a pas à obtenir une certaine valeur. valeur.

CBC doit leur donner des valeurs. La plupart d'entre eux vont à 0 mais certains d'entre eux obtiennent la valeur de la limite supérieure de la variable qui est 1440. Pourquoi est-ce? Est-ce que CBC donne ces valeurs à ces variables? Y a-t-il une règle que le sovler suit? Si vous ne comprenez pas quelque chose, faites-le moi savoir si je peux ajouter des informations ou reformuler, je suis nouveau à ce sujet. Je vous remercie.

Answer 1

Je crois que le solveur CBC fait habituellement une recherche B 'standard' B & B, résolvant une séquence de relaxations LP alors qu'il cherche dans l'arbre. Si vous résolvez un LP avec l'une des méthodes simplex, alors typiquement le processus de recherche pour ce LP marche sur la surface de l'espace possible, donc il est commun pour les variables autrement sous-contraintes de prendre leur valeur limite supérieure ou inférieure .