We propose solution strategies for hard Mixed Integer Programming (MIP) problems, with a focus on distributed parallel MIP optimization. Although our proposals are inspired by the Less-than-truckload (LTL) freight routing problem, they are more generally applicable to hard MIPs from other domains. We start by developing an Integer Programming model for the Less-than-truckload (LTL) freight routing problem, and present a novel heuristic for solving the model in a reasonable amount of time on large LTL networks. Next, we identify some adaptations to MIP branching strategies that are useful for achieving improved scaling upon distribution when the LTL routing problem (or other hard MIPs) are solved using parallel MIP optimization. Recognizing that our model represents a pseudo-Boolean optimization problem (PBO), we leverage solution techniques used by PBO solvers to develop a CPLEX based look-ahead solver for LTL routing and other PBO problems. Our focus once again is on achieving improved scaling upon distribution. We also analyze a technique for implementing subtree parallelism during distributed MIP optimization. We believe that our proposals represent a significant step towards solving big-data driven optimization problems (such as the LTL routing problem) in a more efficient manner. / Thesis / Doctor of Philosophy (PhD) / Less-than-truckload (LTL) freight transportation is a vital part of Canada's economy, with revenues running into billions of dollars and a cascading impact on many other industries. LTL operators often have to deal with large volumes of shipments, unexpected changes in traffic conditions, and uncertainty in demand patterns. In an industry that already has low profit margins, it is therefore vitally important to make good routing decisions without expending a lot of time. The optimization of such LTL freight networks often results in complex big-data driven optimization problems. In addition to the challenge of finding optimal solutions for these problems, analysts often have to deal with the complexities of big-data driven inputs. In this thesis we develop several solution strategies for solving the LTL freight routing problem including an exact model, novel heuristics, and techniques for solving the problem efficiently on a cluster of computers. Although the techniques we develop are inspired by LTL routing, they are more generally applicable for solving big-data driven optimization problems from other domains. Experiments conducted over the years in consultation with industry experts indicate that our proposals can significantly improve solution quality and reduce time to solution. Furthermore, our proposals open up interesting avenues for future research.

This dissertation examines the challenges associated with disruptions in supply chain financing and the railway transportation network. The study is divided into six chapters: In Chapter 1, we introduce the core problems under investigation. Chapter 2 investigates supply chain financing, emphasizing trade credit and bank credit—two predominant external financing mechanisms. Given the inherent uncertainties in demand, interest rates, and supplier credit ratings, this chapter introduces a stochastic programming model accounting for demand uncertainty. Subsequently, a robust optimization program is applied, whose complexity demands a specialized solution methodology. By analyzing a case study centered around a prominent U.S. retailer, the research reveals key insights into decision-making processes related to financing, the effects of bargaining power on portfolio mix and profits, and the relative importance of interest rate uncertainties over supplier credit ratings. Chapter 3 introduces a game-theoretical model designed to hedge financing risks in supply chains, with a focus on the application of insurance for both trade and bank credits. To support the design of effective supply chain finance contracts, three distinct contracts are developed, aiming to synchronize both financial and material flows within the supply chain. A significant feature of this chapter is the data-driven approach employed to address the potential bankruptcy risks that can arise from borrowing loans. Alongside this, a novel solution algorithm is introduced to solve the proposed non-convex models. A case study involving Ford Motor Company and a Chicago-based retailer enriches the research with real-world context. The findings offer several managerial insights: the strategic advantages of different insurance services vary based on the risk attitudes and profit margins of participants. For example, when a retailer operates with a lower profit margin, the use of Trade Credit Insurance (TCI) is recommended in conjunction with a risk-seeking retailer, while a risk-averse retailer might diminish the benefits of TCI. Conversely, with high profit margin retailers, the adoption of Payment Protection Insurance (PPI) is advised under all conditions. In Chapter 4, a game-theoretical model for risk mitigation within railway transportation is introduced. This model addresses random disruptions by employing strategies like repair, re-routing, third-party services, and leasing capacity from competing rail companies. Through a U.S. case study, the efficacy of these strategies is examined, with renting railcars emerging as a particularly potent approach to enhance resilience and reduce third-party expenses. The research further suggests that negotiations extending delivery dates can significantly diminish post-disruption costs. Finally, Chapter 5 summarizes the primary contributions of this research, laying the groundwork for prospective studies in this domain. / Thesis / Doctor of Philosophy (PhD)

Le domaine de recherche de cette thèse est l'optimisation linéaire robuste en deux étapes. Nous sommes intéressés par des algorithmes d'exploration de sa structure et aussi pour ajouter des alternatives afin d'atténuer le conservatisme inhérent à une solution robuste. Nous développons des algorithmes qui incorporent ces alternatives et sont personnalisés pour fonctionner avec des exemples de problèmes à moyenne ou grande échelle. En faisant cela, nous expérimentons une approche holistique du conservatisme en optimisation linéaire robuste et nous rassemblons les dernières avancées dans des domaines tels que l'optimisation robuste basée sur les données, optimisation robuste par distribution et optimisation robuste adaptative. Nous appliquons ces algorithmes dans des applications définies du problème de conception / chargement du réseau, problème de planification, problème combinatoire min-max-min et problème d'affectation de la flotte aérienne. Nous montrons comment les algorithmes développés améliorent les performances par rapport aux implémentations précédentes. / The research scope of this thesis is two-stage robust linear optimization. We are interested in investigating algorithms that can explore its structure and also on adding alternatives to mitigate conservatism inherent to a robust solution. We develop algorithms that incorporate these alternatives and are customized to work with rather medium or large scale instances of problems. By doing this we experiment a holistic approach to conservatism in robust linear optimization and bring together the most recent advances in areas such as data-driven robust optimization, distributionally robust optimization and adaptive robust optimization. We apply these algorithms in defined applications of the network design/loading problem, the scheduling problem, a min-max-min combinatorial problem and the airline fleet assignment problem. We show how the algorithms developed improve performance when compared to previous implementations.

Shorter product life cycles and rapid product obsolescence provide increasing incentives to introduce newproducts to markets more quickly. As a consequence of rapidly changing market conditions, firms focus onimproving their new product development processes to reap the benefits of early market entry. Researchershave analyzed market entry, but have seldom provided quantitative approaches for the product rolloverproblem. This research builds upon the literature by using established optimization methods to examine howfirms can minimize their net loss during the rollover process. Specifically, our work explicitly optimizes thetiming of removal of old products and introduction of new products, the optimal strategy, and the magnitudeof net losses when the market entry approval date of a new product is unknown. In the first paper, we use theconditional value at risk to optimize the net loss and investigate the effect of risk perception of the manageron the rollover process. We compare it to the minimization of the classical expected net loss. We deriveconditions for optimality and unique closed-form solutions for single and dual rollover cases. In the secondpaper, we investigate the rollover problem, but for a time-dependent demand rate for the second producttrying to approximate the Bass Model. Finally, in the third paper, we apply the data-driven optimizationapproach to the product rollover problem where the probability distribution of the approval date is unknown.We rather have historical observations of approval dates. We develop the optimal times of rollover and showthe superiority of the data-driven method over the conditional value at risk in case where it is difficult to guessthe real probability distribution

[pt] Otimização de portfólio tradicionalmente assume ter conhecimento da distribuição de probabilidade dos retornos ou pelo menos algum dos seus momentos. No entanto, é sabido que a distribuição de probabilidade dos retornos muda com frequência ao longo do tempo, tornando difícil a utilização prática de modelos puramente estatísticos, que confiam indubitavelmente em uma distribuição estimada. Em contrapartida, otimização robusta considera um completo desconhecimento da distribuição dos retornos, e por isto, buscam uma solução ótima para todas as realizações possíveis dentro de um conjunto de incerteza dos retornos. Mais recentemente na literatura, técnicas de distributionally robust optimization permitem lidar com a ambiguidade com relação à distribuição dos retornos. No entanto essas técnicas dependem da construção do conjunto de ambiguidade, ou seja, distribuições de probabilidade a serem consideradas. Neste trabalho, propomos a construção de conjuntos de ambiguidade poliédricos baseado somente em uma amostra de retornos. Nestes conjuntos, as relações entre variáveis são determinadas pelos dados de maneira não paramétrica, sendo assim livre de possíveis erros de especificação de um modelo estocástico. Propomos um algoritmo para construção do conjunto e, dado o conjunto, uma reformulação computacionalmente tratável do problema de otimização de portfólio. Experimentos numéricos mostram que uma melhor performance do modelo em comparação com benchmarks selecionados. / [en] Portfolio optimization traditionally assumes knowledge of the probability distribution of returns or at least some of its moments. However is well known that the probability distribution of returns changes over time, making difficult the use of purely statistic models which undoubtedly rely on an estimated distribution. On the other hand robust optimization consider a total lack of knowledge about the distribution of returns and therefore it seeks an optimal solution for all the possible realizations wuthin a set of uncertainties of the returns. More recently the literature shows that distributionally robust optimization techniques allow us to deal with ambiguity regarding the distribution of returns. However these methods depend on the construction of the set of ambiguity, that is, all distribution of probability to be considered. This work proposes the construction of polyhedral ambiguity sets based only on a sample of returns. In those sets, the relations between variables are determined by the data in a non-parametric way, being thus free of possible specification errors of a stochastic model. We propose an algorithm for constructing the ambiguity set, and then a computationally treatable reformulation of the portfolio optimization problem. Numerical experiments show that a better performance of the model compared to selected benchmarks.

Les consommateurs d’aujourd’hui ont des goûts très variés et cherchent les produits les plus récents. Avec l’accélération technologique, les cycles de vie des produits se sont raccourcis et donc, de nouveaux produits doivent être introduits au marché plus souvent et progressivement, les anciens doivent y être retirés. L’introduction d’un nouveau produit est une source de croissance et d’avantage concurrentiel. Les directeurs du Marketing et Supply Chain se sont confrontés à la question de savoir comment gérer avec succès le remplacement de leurs produits et d’optimiser les coûts de la chaîne d’approvisionnement associée. Dans une situation idéale, la procédure de rollover est efficace et claire: l’ancien produit est vendu jusqu’à une date prévue où un nouveau produit est introduit. Dans la vie réelle, la situation est moins favorable. Le but de notre travail est d’analyser et de caractériser la politique optimale du rollover avec une date de disponibilitéstochastique pour l’introduction du nouveau produit sur le marché. Pour résoudre le problème d’optimisation,nous utilisons dans notre premier article deux mesures de minimisation: le coût moyen et le coût de la valeurconditionnelle à risque. On obtient des solutions en forme explicite pour les politiques optimales. En outre, nous caractérisons l’influence des paramètres de coûts sur la structure de la politique optimale. Dans cet esprit, nous analysons aussi le comportement de la politique de rollover optimale dans des contextes différents. Dans notre deuxième article, nous examinons le même problème mais avec une demande constante pour le premier produit et une demande linéaire au début puis constante pour le deuxième. Ce modèle est inspiré par la demande de Bass. Dans notre troisième article, la date de disponibilité du nouveau produit existe mais elle est inconnue. La seule information disponible est un ensemble historique d’échantillons qui sont tirés de la vraie distribution. Nous résoudrons le problème avec l’approche data drivenet nous obtenons des formulations tractables. Nous développons aussi des bornes sur le nombre d’échantillons nécessaires pour garantir qu’avec une forte probabilité, le coût n’est pas très loin du vrai coût optimal. / Shorter product life cycles and rapid product obsolescence provide increasing incentives to introduce newproducts to markets more quickly. As a consequence of rapidly changing market conditions, firms focus onimproving their new product development processes to reap the benefits of early market entry. Researchershave analyzed market entry, but have seldom provided quantitative approaches for the product rolloverproblem. This research builds upon the literature by using established optimization methods to examine howfirms can minimize their net loss during the rollover process. Specifically, our work explicitly optimizes thetiming of removal of old products and introduction of new products, the optimal strategy, and the magnitudeof net losses when the market entry approval date of a new product is unknown. In the first paper, we use theconditional value at risk to optimize the net loss and investigate the effect of risk perception of the manageron the rollover process. We compare it to the minimization of the classical expected net loss. We deriveconditions for optimality and unique closed-form solutions for single and dual rollover cases. In the secondpaper, we investigate the rollover problem, but for a time-dependent demand rate for the second producttrying to approximate the Bass Model. Finally, in the third paper, we apply the data-driven optimizationapproach to the product rollover problem where the probability distribution of the approval date is unknown.We rather have historical observations of approval dates. We develop the optimal times of rollover and showthe superiority of the data-driven method over the conditional value at risk in case where it is difficult to guessthe real probability distribution