ABSTRACT. Chance constrained programs, which seek for a cost-optimal decision that satisfies a set of uncertain constraints with a pre-specified probability, constitute a popular and versatile method for decision-making under uncertainty. Since the true distribution governing the uncertain problem parameters is typically not known and thus has to be estimated from data, chance constrained programs often suffer from overfitting. In this talk, we study data-driven chance constrained programs that combat the issue of overfitting by  hedging against all distributions sufficiently close to the empirical one, where proximity is measured by the Wasserstein distance. For individual chance constraints as well as joint chance constraints with right-hand side uncertainty, we provide exact mixed-integer conic programming reformulations. Using our reformulation, we show that two popular approximation schemes based on the conditional-value-at-risk and the Bonferroni inequality can perform poorly in practice. We conclude with numerical results.

ABSTRACT. Le travail présenté a été réalisé au cours d'un stage de recherche au sein du laboratoire d'informatique de l'Ecole polytechnique (LIX), sous la direction de Leo Liberti et Claudia d'Ambrosio, dans le cadre de la formation du Master Parisien de Recherche Opérationnelle (MPRO). Il porte sur l'application d'une méthode de faisceaux pour résoudre une large gamme de relaxations pour des problèmes d'optimisation polynomiale de grande taille.

ABSTRACT. L’algorithme du simplexe reste un des algorithmes les plus utilisés pour résoudre les problèmes de programmation linéaire. Ses performances pratiques sont reconnues. Il reste cependant de nombreuses questions concernant son analyse théorique. En particulier, la question ouverte la plus importante est de savoir s’il existe une règle de pivotage qui permette de faire tourner l’algorithme en temps polynomial dans le pire cas. Il est probablement trop difficile d’attaquer ce problème directement. Il est cependant intéressant d’étudier des cas particuliers de polyèdres et de règles de pivotage. On peut par exemple étudier le cas de polyèdres topologiquement équivalents à un cube. Klee et Minty ont montré que la règle de pivotage de Dantzig pouvait un prendre un nombre exponentiel d’étapes sur un cube déformé. Dans ce projet, nous étudions la règle de pivotage de « greatest improvement » sur les cubes déformés.

ABSTRACT. We investigate a stochastic variant of the well-known 1|r_j|sum w_jU_j problem, in which the jobs are subject to unexpected failure that incur additional costs. The decision maker is then allowed to take recourse actions such as outsourcing or spending more time on the jobs to fix them. We are interested in worst-case optimization, with polyhedral uncertainty set affecting the objective function.

In our problem, called Two-Stage Robust Weighted Number of Tardy Jobs (2SRWNTJ) in the sequel, an instance consists of a set of jobs J, each of which is characterized by a release date r_j, a due date d_j, and a nominal processing time p_j. A weight w_j can be interpreted as the cost for executing the job, or as the opposite of the profit associated with the processing of the job. At first stage, here-and-now decisions are to select a subset of jobs J^* (among J) to process. After that, a subset of the jobs can be affected by unexpected failures, those being governed by the uncertainty set Xi = { xi in R^{|J|}_+ | xi_j <= 1, for all J_j in J and sum_{j|J_j in J} xi_j <= Gamma }. The realization of alea xi in Xi determines a profit degradation for each job J_j in J defined as delta_j xi_j, where delta_j is the maximum additional cost linked to the job's failure. Input parameter Gamma is, therefore, the largest number of jobs that can incur their maximum degradation. At second stage, recourse actions have to be taken. For each J^*, one can choose (i) to keep the revealed profit ; (ii) to repair the job, adding tau_j time units to its processing time to recover its initial profit ; or (iii) to reject the job and pay a fixed outsourcing cost f_j. Finally, jobs in J^* that are not rejected must be scheduled so that they meet their time windows. The objective is to select a subset of jobs as well as the recourse actions that minimize the worst-case overall cost.

The main contribution of our work is to propose the first exact method for this problem. It is based on a recent advances in two-stage robust optimization with objective uncertainty. In particular, we first model the (2SRWNTJ) problem as a standard two-stage robust problem with second-stage integer decisions by extending some results for the deterministic 1|r_j|\sum w_jU_j problem. We then show how the methodology recently introduced for two-stage robust problems with objective uncertainty can be used to reformulate our problem as a MILP formulation. The application of the aforementioned method is motivated by some interesting features of our initial formulation. Namely, a polyhedral uncertainty set and interdiction linking constraints between the first stage and second stage (i.e., constraints of the form alpha <= beta where alpha and beta are binary decisional vectors).

Because the obtained formulation is of exponential size, we solve it with a branch-and-price algorithm. Finally, we compare our approach with the previously mentioned finite adaptability heuristic. We show that our exact approach outperforms it for the most difficult instances, namely, those with a larger number of jobs. In particular, we are able to solve to optimality all 20-jobs instances of our test bed within one hour, and 85% of the 25-jobs instances within the same time limit while the finite adaptability approach fails at solving some 10 jobs-instances, even by assuming to know the optimal parameter K^*. Finally, it solves less than 17% of the instances for which K^* >= 2 and |J| = 25.

ABSTRACT. Strong RLT1 bounds

for some quadratic 0–1 optimization problems

with linear constraints,

computed from decomposable Lagrangean relaxations

Monique Guignard¹, Jongwoo Park²

¹ University of Pennsylvania, the Wharton School, OIDD Dept., Philadelphia, PA 19104, USA

guignard_monique@yahoo.fr

² University of Pennsylvania, School of Engineering and Applied Sciences, ESE Dept., Philadelphia. PA 19104, USA

jongwpnice@gmail.com

Keywords   quadratic optimization in 0-1variables, decomposable Lagrangean relaxation.

The purpose of this research is to generate quickly strong bounds for pure (0-1) quadratic problems with linear constraints. The basis of our approach is the classical Reformulation Linearization Technique (RLT) of Sherali and Adams (1986, 1990). When applied to a pure 0-1 quadratic optimization problem with linear constraints (P), RLT constructs a hierarchy of LP (i.e., continuous and linear) models of increasing sizes, which provide monotonically improving continuous bounds on the optimal value of (P) as the level, i.e., the stage in the process, increases. When the level reaches the dimension of the original solution space, the last model provides an LP bound equal to the IP optimum. In practice, unfortunately, the problem size increases so rapidly that for large instances, even computing bounds for RLT models of level k (called RLTk) for small k may be challenging. To our knowledge, only results for bounds of levels 1, 2, and 3 have been reported in the literature.

We are proposing, for certain quadratic problem types, a way of producing stronger bounds than continuous RLT1 bounds in a fraction of the time it would take to compute continuous RLT2 bounds. The approach consists in applying a specific decomposable Lagrangean relaxation to a specially constructed RLT1-type linear 0–1 model. If the overall Lagrangean problem does not have the integrality property, and if it can be solved easily as a 0–1 rather than a continuous problem, one obtains 0–1 RLT1 bounds that may be of roughly the same quality as standard continuous RLT2 bounds, but in a fraction of the time and with much smaller storage requirements. In (Guignard 2018), the quality of the bounds was ascertained for a few problem types, but the actual decomposition into smaller 0-1 subproblems was not actually implemented. We have now shown that the same exact bounds as in the paper can be obtained via full decomposition of the Lagrangean models in similar or even smaller computer times, and that, as problem size increases, the actual decomposition of the Lagrangean problem into a number of smaller subproblems makes it possible to compute such bounds for much larger instances.

We will present numerical results for the Cross-dock Door Assignment Problem, which is a special case of the Generalized Quadratic Assignment Problem, and for the 0–1 Quadratic Knapsack Problem. These show that just solving one decomposable Lagrangean relaxation problem in 0–1 variables produces a bound stronger than the standard continuous RLT1 bound, and can be close to the standard continuous RLT2 bound (when available) but can be computed much faster, especially for larger instances.

References

[1] Adams, W. P. & Sherali H. D. (1986). A Tight Linearization and an Algorithm for Zero-One Quadratic Programming Problems. 

Management Science, 32(10), 1274-1290.

[2] Sherali, H. D. & Adams, W. P. (1990). A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems.

SIAM Journal on Discrete Mathematics, 3(3), 411–430.

[3] Guignard, M. (2006). RLT1 and LR for the GQAP.

OPIM Department Research Report 06-06-01, the Wharton School, University of Pennsylvania.

[4] Adams, W. P., Guignard, M., Hahn, P. M., Hightower, W. L. (2007).  A level-2 reformulation–linearization technique bound for the quadratic assignment problem.

European Journal of Operational Research, 180(3), 983-996.

[5] Pessoa, A. A., Hahn, P. M., Guignard, M. & Zhu, Yi-Rong (2010). Algorithms for the generalized quadratic assignment problem combining Lagrangean decomposition and the Reformulation-Linearization Technique.

Received the first prize at the SOBRAPO meeting, Brazil, 2008.     

European Journal of Operational Research, 206(1), 54-63.

[6] Hahn, P. M., Zhu, Yi-Rong, Guignard, M., Hightower, W. L. and Saltzman, M. J. (2012). A level-3 reformulation-linearization technique bound for the quadratic assignment problem.  

INFORMS Journal on Computing, 24(2), 202–209.

[7] Park, J. (2014). Generalized quadratic assignment problem: Combining level 1 Lagrangean decomposition and reformulation-linearization technique.

Independent Study Report, University of Pennsylvania, ESE Department.

[8] Guignard, M. (2018). Strong RLT1 bounds from decomposable Lagrangean relaxation for some quadratic 0-1 optimization problems with linear constraints.

Annals of Operations Research, DOI 10.1007/s10479-018-3092-8.

[9] Park, J. & Guignard, M. (2018). Computing bounds for CDAP problems using RLT1 + LR + ILP decomposition. 

OID Department Research Report, the Wharton School, University of Pennsylvania.

ABSTRACT. La biologie des systèmes est un domaine récent proposant d’étudier les organismes vivants tels qu’ils se presentent en réalité. La comprehension du fonctionnement de ces organismes necessite des algorithmes de traitement et d’analyse de plus en plus spécialisés et efficaces. De nombreuses approches destinées à la comparaison de réseaux biologiques (homogènes ou hétérogènes) reposent sur des modèles de graphe. L’objectif de ce papier est la détection de réactions voisines catalysées par des produits de gènes voisins, où la notion de voisinage peut être modulée en autorisant que certaines réactions et/ou gènes soient omis.

ABSTRACT. Le sujet du stage est d'optimiser le dépôt de couches de matériaux sur des plaques de verre. L'objectif est de minimiser les pertes lorsque certains matériaux sont renouvelés. Cette optimisation utilise des prévisions sur les demandes de production, mais il y a de l'incertitude sur la réalisation de ces prévisions. Ainsi, notre modélisation du problème tient compte des aléas sur les demandes de production. Nous construisons des stratégies de production réalisables dans tous les cas, et nous minimisons aussi le coût de la solution dans le pire des cas. Les aléas apparaissent successivement dans le temps. Nous proposons donc un modèle robuste avec des variables de recours. La méthode que nous avons mise en place propose une solution robuste dont la valeur s'approche à moins de 1% de la valeur optimale pour des données réelles de deux mois de production lorsque les caractéristiques de l'aléa considéré sont une variation maximale de 10% des temps de production des matériaux. Cette solution robuste est obtenue en moins de 20 minutes avec un ordinateur portable d'entrée de gamme à l'aide du solveur Cplex.

ABSTRACT. Lors de ce stage, nous nous intéressons au problème de câblage optique, un problème de conception de réseaux s’inscrivant parmi les défis actuels majeurs des opérateurs de télécommunication. Concernant le remplacement des réseaux de cuivre par des réseaux de fibres optiques. Ce stage s’inscrit dans la suite des travaux effectués par V. Angilella et L. Alves Cota, qui ont principalement travaillé sur différentes formulations du problème de câblage optique. En partant de leurs travaux, nous avons cherché à optimiser nos méthodes de résolution du problème de câblage optique. Pour cela, nous avons enrichi le modèle à l’aide de plusieurs familles d’inégalités valides, nous avons également fait la découverte de plusieurs propriétés spécifiques à notre problème. Nous avons testé l’apport de nos inégalités valides sur des instances réelles et les résultats obtenus sont encourageants. De plus, nous avons également chercher à résoudre ce problème via un algorithme de Branch & Price ; nous présenterons le problème de pricing ainsi que la procédure de génération de colonnes.

ABSTRACT. Most operations research problems require demand data as input. In practice, aggregate representations of demand are commonly used. The Demand-based Revenue Maximization Model considered here is an application of a general framework allowing the integration of advanced Discrete Choice Models (that model the demand aspects) into a Mixed Integer Linear Programming formulation.

Due to the disaggregate representation of the demand and the linear formulation, the resulting problem is computationally expensive to solve. Thus, algorithms have been developed in order to improve the solving efficiency. Among them, a Lagrangian decomposition is implemented and applied to several variants of the Subgradient Optimization Method. Various enhancement techniques are also considered. Finally, two promising heuristics have also been designed and compared to the CPLEX solver.

ABSTRACT. CPLEX Optimization Studio 12.10 was released in December 2019, and this talk will provide an overview of these recent development. With this new version, CP Optimizer now has callbacks to monitor the state of the search, and can track Key Performance Indicators. CPLEX got a BRANCHING context in the new Generic Callback. And the performance of both engines were significantly improved, specifically for feasibility problems in CP Optimizer, and MIQCP and Benders in CPLEX, with respective speedups of 5x, 1.9x and 2.8x.

ABSTRACT. DOC v4 / DB Gene est une plateforme qui aide à développer, déployer et lancer des applications d’optimisation rapidement, facilement et efficacement. DOC v4 / DB Gene est orienté composants et peut-être configuré et personnalisé. Reposant sur des technologies open source largement adoptées, cette plateforme réduit significativement l’effort, le temps et le risque associés à la création d’applications sur mesure. Un exemple d'application DOC v4 / DB Gene, ainsi que les interactions possibles avec une telle application, seront démontrés lors de cette présentation.