Search

In this paper, we define a new variant of the knapsack problem, the Symmetric Weight Matrix Knapsack Problem (SMKP). The (SMKP) is the core structure of the Hydro Unit Commitment being a production scheduling problem relative to hydroelectric units. The (SMKP) is proven to be NP-hard. The main contribution is a polyedral study of the (SMKP) and a dedicated two-phase Branch & Cut scheme. The polyedral study focuses on inequalities with 0-1 coefficients. Necessary facet-defining conditions are described, through a new structure called pattern encoding the symmetries of the (SMKP). A special case of patterns is identified where these conditions are necessary and sufficient. A two-phase Branch & Cut scheme is defined to exploit the symmetries on the pattern inequalities. As a pre-processing step, the first phase aims to produce patterns verifying these conditions. The second phase separates the inequalities associated to the patterns produced in the first phase at the nodes of a Branch & Cut tree. Experimental results demonstrate the efficiency of the proposed scheme in particular with respect to default CPLEX.

Variantes du polytope min-up/min-down

The Min-up/min-down Unit Commitment Problem (MUCP), is to find a minimum-cost production plan on a discrete time horizon for a set of units producing electric power. At each time period, the total production has to meet a forecast demand. Each unit must satisfy minimum up and down time constraints. We show that the MUCP is strongly NP-hard, thus highlighting that the dynamic coupling of demands by minimum up and down time constraints represents one major source of difficulty. To cope with this difficulty, we introduce interval up-set inequalities, a new class of valid inequalities for the MUCP polytope, generalizing both min-up and extended cover inequalities from the 0-1 knapsack polytope. Facet defining cases are characterized and a Branch & Cut algorithm is devised. To deal with the symmetries impairing the solution process, we define sub-symmetries, as symmetries arising from a solution subset. We focus on integer linear programs whose (sub-)symmetry groups are symmetric groups acting on sub-columns of solution matrices. We propose a general framework to handle sub-symmetries in such problems. On this basis, two symmetry-breaking techniques are introduced. The first technique is an orbitopal fixing algorithm for the full (sub-)orbitope. The second technique is based on sub-symmetry breaking inequalities. Experimental results on MUCP instances show that the proposed techniques outperform state-of-the-art techniques. Finally we compare various Dantzig-Wolfe structures for the MUCP. We show that good quality lower bounds can be obtained by dualization of time-coupling constraints. Branch & Price results show that interval up-set inequalities are useful in this context.; Le Min-up/min-down Unit Commitment Problem (MUCP) consiste à trouver un plan de production de coût minimum pour un ensemble d’unités de production électrique sur un intervalle de temps discrétisé. A chaque pas de temps, la production totale doit satisfaire la demande prévue. Chaque unité respecte des temps minimum de marche et d’arrêt. Nous montrons que le MUCP est fortement NP-difficile, mettant ainsi en valeur l’impact du couplage dynamique des contraintes de demande sur la difficulté du problème. Pour appréhender cette difficulté, nous introduisons les inégalités interval up-set, généralisant les contraintes de min-up et les extended cover du sac à dos. Les facettes sont caractérisées, et un Branch & Cut est implémenté. Afin de briser les symétries du problème, nous définissons les sous-symétries comme des symétries apparaissant dans des sous-ensembles de solution. Nous considérons des PLNE dont les groupes de sous-symétrie sont des groupes symétriques agissant sur certaines sous-colonnes des matrices solutions. Nous proposons un cadre générique pour gérer les sous-symétries apparaissant dans ce type de problèmes. Deux techniques pour briser les sous-symétries sont proposées : la première est un algorithme de fixing orbitopal pour le full sub-orbitope, la seconde est basée sur des inégalités. Les résultats expérimentaux montrent que les techniques proposées sont plus performantes que les techniques de la littérature. Enfin, nous comparons différentes structures de décomposition pour le MUCP. Des bornes de bonne qualité sont obtenues par dualisation des contraintes dynamiques. Notre Branch&Price&Cut montre que les interval up-set sont utiles dans ce contexte.

The Min-up/min-down Unit Commitment Problem (MUCP), is to find a minimum-cost production plan on a discrete time horizon for a set of units producing electric power. At each time period, the total production has to meet a forecast demand. Each unit must satisfy minimum up and down time constraints. We show that the MUCP is strongly NP-hard, thus highlighting that the dynamic coupling of demands by minimum up and down time constraints represents one major source of difficulty. To cope with this difficulty, we introduce interval up-set inequalities, a new class of valid inequalities for the MUCP polytope, generalizing both min-up and extended cover inequalities from the 0-1 knapsack polytope. Facet defining cases are characterized and a Branch & Cut algorithm is devised. To deal with the symmetries impairing the solution process, we define sub-symmetries, as symmetries arising from a solution subset. We focus on integer linear programs whose (sub-)symmetry groups are symmetric groups acting on sub-columns of solution matrices. We propose a general framework to handle sub-symmetries in such problems. On this basis, two symmetry-breaking techniques are introduced. The first technique is an orbitopal fixing algorithm for the full (sub-)orbitope. The second technique is based on sub-symmetry breaking inequalities. Experimental results on MUCP instances show that the proposed techniques outperform state-of-the-art techniques. Finally we compare various Dantzig-Wolfe structures for the MUCP. We show that good quality lower bounds can be obtained by dualization of time-coupling constraints. Branch & Price results show that interval up-set inequalities are useful in this context.; Le Min-up/min-down Unit Commitment Problem (MUCP) consiste à trouver un plan de production de coût minimum pour un ensemble d’unités de production électrique sur un intervalle de temps discrétisé. A chaque pas de temps, la production totale doit satisfaire la demande prévue. Chaque unité respecte des temps minimum de marche et d’arrêt. Nous montrons que le MUCP est fortement NP-difficile, mettant ainsi en valeur l’impact du couplage dynamique des contraintes de demande sur la difficulté du problème. Pour appréhender cette difficulté, nous introduisons les inégalités interval up-set, généralisant les contraintes de min-up et les extended cover du sac à dos. Les facettes sont caractérisées, et un Branch & Cut est implémenté. Afin de briser les symétries du problème, nous définissons les sous-symétries comme des symétries apparaissant dans des sous-ensembles de solution. Nous considérons des PLNE dont les groupes de sous-symétrie sont des groupes symétriques agissant sur certaines sous-colonnes des matrices solutions. Nous proposons un cadre générique pour gérer les sous-symétries apparaissant dans ce type de problèmes. Deux techniques pour briser les sous-symétries sont proposées : la première est un algorithme de fixing orbitopal pour le full sub-orbitope, la seconde est basée sur des inégalités. Les résultats expérimentaux montrent que les techniques proposées sont plus performantes que les techniques de la littérature. Enfin, nous comparons différentes structures de décomposition pour le MUCP. Des bornes de bonne qualité sont obtenues par dualisation des contraintes dynamiques. Notre Branch&Price&Cut montre que les interval up-set sont utiles dans ce contexte.