Faculté des arts et des sciences – Département d'informatique et de recherche opérationnelle - Travaux et publications

URI permanent de cette collectionhttps://hdl.handle.net/1866/19207

Cette collection accueille les publications savantes et d’autres types de travaux d’auteur.e.s associé.e.s à cette unité. Voir aussi la collection Thèses et mémoires de l'unité.

Parcourir

Voici les éléments 1 - 16 sur 16

Accès libre
Integer programming games
Carvalho, Margarida; Dragotto, Gabriele; Lodi, Andrea; Sankaranarayanan, Sriram; Université de Montréal. Faculté des arts et des sciences. Département d'informatique et de recherche opérationnelle (Foundations and Trends®, 2025-02-20)
We provide a comprehensive survey of Integer Programming Games (IPGs), focusing on both simultaneous games and bilevel programs. These games are characterized by integral constraints within the players’ strategy sets. We start from the fundamental definitions of these games and various solution concepts associated with them, and derive the properties of the games and the solution concepts. For each of the two types of games – simultaneous and bilevel – we have one section dedicated to the analysis of the games and another section dedicated to the development and analyses of algorithms to solve them. The analyses sections present results on the computational complexity of the general game as well as various other restricted versions. These sections also discuss the structural properties of the games and the equilibrium concepts associated with them. The algorithm sections, in contrast, present some of the state-of-the-art algorithms developed to solve these games, either exactly, approximately or fast under fixed-parameter assumptions. These sections also contain proofs of the correctness of these algorithms and an assessment of their theoretical run times in the worst-case scenario.
Embargo
A new integrated cooperative game and optimization model for the allocation of forest resources
Rahmoune, Mahdi; Radjef, Mohammed Said; Boukherroub, Tasseda; Carvalho, Margarida; Université de Montréal. Faculté des arts et des sciences. Département d'informatique et de recherche opérationnelle (Elsevier, 2024-01-19)
We propose an integrated approach combining a cooperative game model and a multi-objective optimization model to determine the quantities of forest resources to allocate to several mills. The new mechanism developed in this study is applied to a regional case study in the province of Quebec (Canada), where public-owned forest resources should be allocated by the government to multiple competing mills. Collaboration between mills is considered in the upstream supply chain (i.e., harvesting, road construction/upgrading, and transportation operations) as well as their individual sustainability performances (economic, environmental and social aspects) in the allocation process. Moreover, this approach highlights the conditions under which the allocation ensures the stability of the configuration of the coalitions through a coalitional stability analysis. The proposed approach attempts to capture collaboration benefits and mills’ individual performances in the allocation process, while promoting equity among them. The coalitions of the case study overlap and thus, the concept of coalition configuration value is used to measure the marginal contribution of each mill to the cost savings. In particular, a methodology is proposed for the estimation of this value based on real data. The results of this study demonstrate that the allocation honors the efforts made by mills, both individually and collectively. In addition, it stimulates them towards a sustainable resource management relationship.
Embargo
Integration of sales and operations : a dynamic mixed-integer programming game
Telha, Claudio; Carvalho, Margarida; Université de Montréal. Faculté des arts et des sciences. Département d'informatique et de recherche opérationnelle (Springer, 2024-07-29)
We define a framework to investigate and assess the impact of prompt and dynamic reactions to market competition in production planning problems. It depicts two firms that produce and sell substitutable products over a finite time horizon. Each firm optimizes its sales and production costs, and has sufficient market power to affect the sales of the other firm. The framework can capture several production and market competition features. We model production plans using mixed-integer programs and market competition using sequential Stackelberg games. Under certain conditions, we can solve the models in our framework in polynomial-time. We provide examples to illustrate how the framework can match the requirements of production planning and sales. Then, we perform a computational study to analyze a planning problem that features the possibility of technological investments to reduce the variable production costs. We draw insights on the value of our polynomial-time method to compute subgame perfect equilibria by comparing its optimal production plans against a static model, where firms fix the entire production plan at the beginning of the planning horizon, and a myopic model, where firms ignore the impact that current decisions will have in future periods.
Accès libre
Reconstruction of machine-made shapes from bitmap sketches
Puhachov, Ivan; Martens, Cedric; Kry, Paul G.; Bessmeltsev, Mikhail; Université de Montréal. Faculté des arts et des sciences. Département d'informatique et de recherche opérationnelle (Association for computing machinery, 2023-12)
We propose a method of reconstructing 3D machine-made shapes from bitmap sketches by separating an input image into individual patches and jointly optimizing their geometry. We rely on two main observations: (1) human observers interpret sketches of man-made shapes as a collection of simple geometric primitives, and (2) sketch strokes often indicate occlusion contours or sharp ridges between those primitives. Using these main observations we design a system that takes a single bitmap image of a shape, estimates image depth and segmentation into primitives with neural networks, then fits primitives to the predicted depth while determining occlusion contours and aligning intersections with the input drawing via optimization. Unlike previous work, our approach does not require additional input, annotation, or templates, and does not require retraining for a new category of man-made shapes. Our method produces triangular meshes that display sharp geometric features and are suitable for downstream applications, such as editing, rendering, and shading.
Accès libre
Sketch2Pose : estimating a 3D character pose from a bitmap sketch
Brodt, Kirill; Bessmeltsev, Mikhail; Université de Montréal. Faculté des arts et des sciences. Département d'informatique et de recherche opérationnelle (Association for computing machinery, 2022-07-22)
Artists frequently capture character poses via raster sketches, then use these drawings as a reference while posing a 3D character in a specialized 3D software --- a time-consuming process, requiring specialized 3D training and mental effort. We tackle this challenge by proposing the first system for automatically inferring a 3D character pose from a single bitmap sketch, producing poses consistent with viewer expectations. Algorithmically interpreting bitmap sketches is challenging, as they contain significantly distorted proportions and foreshortening. We address this by predicting three key elements of a drawing, necessary to disambiguate the drawn poses: 2D bone tangents, self-contacts, and bone foreshortening. These elements are then leveraged in an optimization inferring the 3D character pose consistent with the artist's intent. Our optimization balances cues derived from artistic literature and perception research to compensate for distorted character proportions. We demonstrate a gallery of results on sketches of numerous styles. We validate our method via numerical evaluations, user studies, and comparisons to manually posed characters and previous work.
Accès libre
Pricing and quality investments in a mixed brown-green product market
Mukherjee, Arka; Carvalho, Margarida; Université de Montréal. Faculté des arts et des sciences. Département d'informatique et de recherche opérationnelle (Springer, 2020-09-22)
Sustainable Supply Chain Management (SSCM) has assumed a position of prominence for academics and industry over the last two decades. The sustainability literature shows that typically manufacturers aim to optimize their pricing and greening level decisions in a mixed (green and brown) consumer market. In this work, we capture a manufacturer’s classic dilemma on the pricing of green and brown products, and greening investments, while subject to budget constraint. We compute and analyze the variations of optimal decisions over time. Our findings underscore the importance of investing in greening technologies and learning for the survival of green products. Furthermore, we show that a manufacturer’s optimal pricing strategy is to enter the market with a lower price for the green product and to increase it over time, eventually, surpassing the price for the brown product. Our analysis reveals that the greening level attraction can nullify the effect of a high price on the green product, resulting in higher green demand than brown. Higher green product demand is a win-win situation for both the manufacturer and the environment.
Accès libre
Lexicographic optimization for the multi-container loading problem with open dimensions for a shoe manufacturer
Vieira, Manuel V. C.; Carvalho, Margarida; Université de Montréal. Faculté des arts et des sciences. Département d'informatique et de recherche opérationnelle (Springer, 2022-08-29)
Motivated by a real-world application, we present a multi-container loading problem with 3-open dimensions. We formulate it as a biobjective mixed-integer nonlinear program with lexicographic objectives in order to reflect the decision maker’s optimization priorities. The first objective is to minimize the number of containers, while the second objective is to minimize the volume of those containers. Besides showing the NP-hardness of this sequential optimization problem, we provide bounds for it which are used in the three proposed algorithms, as well as, on their evaluation when a certificate of optimality is not available. The first is an exact parametric-based approach to tackle the lexicographic optimization through the second objective of the problem. Nevertheless, given that the parametric programs correspond to large nonlinear mixed-integer optimizations, we present a heuristic that is entirely mathematical-programming based. The third algorithm enhances the solution quality of the heuristic. These algorithms are specifically tailored for the real-world application. The effectiveness and efficiency of the devised heuristics is demonstrated with numerical experiments.
Accès libre
A bilevel approach for the collaborative transportation planning problem
Santos, Maria João; Curcio, Eduardo; Amorim, Pedro; Carvalho, Margarida; Marques, Alexandra; Université de Montréal. Faculté des arts et des sciences. Département d'informatique et de recherche opérationnelle (Elsevier, 2020-12-15)
The integration of the outbound and the inbound logistics of a company leads to a large transportation network, allowing to detect backhauling opportunities to increase the efficiency of the transportation. In collaborative networks, backhauling is used to find profitable services in the return trip to the depot and to reduce empty running of vehicles. This work investigates the vertical collaboration between a shipper and a carrier for the planning of integrated inbound and outbound transportation. Based on the hierarchical nature of the relation between the shipper and the carrier and their different goals, the problem is formulated as a bilevel Vehicle Routing Problem with Selective Backhauls (VRPSB). At the upper level, the shipper decides the minimum cost delivery routes and the set of incentives offered to the carrier to perform integrated routes. At the lower level, the carrier decides which incentives are accepted and on which routes the backhaul customers are visited. We devise a mathematical programming formulation for the bilevel VRPSB, where the routing and the pricing problems are optimized simultaneously, and propose an equivalent reformulation to reduce the problem to a single-level VRPSB. The impact of collaboration is evaluated against non-collaborative approaches and two different side payment schemes. The results suggest that our bilevel approach leads to solutions with higher synergy values than the approaches with side payments.
Accès libre
Bilevel knapsack problems
Carvalho, Margarida; Université de Montréal. Faculté des arts et des sciences. Département d'informatique et de recherche opérationnelle (Springer, 2023)
Accès libre
Nash equilibria in the two-player kidney exchange game
Carvalho, Margarida; Lodi, Andrea; Pedroso, João Pedro; Viana, Ana; Université de Montréal. Faculté des arts et des sciences. Département d'informatique et de recherche opérationnelle (Springer, 2016-04-21)
Kidney exchange programs have been set in several countries within national, regional or hospital frameworks, to increase the possibility of kidney patients being transplanted. For the case of hospital programs, it has been claimed that hospitals would benefit if they collaborated with each other, sharing their internal pools and allowing transplants involving patients of different hospitals. This claim led to the study of multi-hospital exchange markets. We propose a novel direction in this setting by modeling the exchange market as an integer programming game. The analysis of the strategic behavior of the entities participating in the kidney exchange game allowed us to prove that the most rational game outcome maximizes the social welfare and that it can be computed in polynomial time.
Accès libre
Dynamic decision making in a mixed market under cooperation : towards sustainability
Mukherjee, Arka; Carvalho, Margarida; Université de Montréal. Faculté des arts et des sciences. Département d'informatique et de recherche opérationnelle (Elsevier, 2021-08-21)
Sustainability goals are becoming a priority in many societies. An important element in this context is the success of environmentally friendly products. Hence, we consider a manufacturer-retailer vertical supply chain model, managing a green product and its conventional counterpart, designated by brown product. We analyze three kinds of dynamic market scenarios: no market leadership, the manufacturer as the market leader, and the retailer as the market leader. Under each scenario, we determine the equilibrium decisions for pricing and greening investments as well as their dependence on a cost-sharing proportion agreement between the firms. We find that generally both firms have similar pricing trends, where the gap between the two product prices increases with the share of cost carried by the retailer. Moreover, we analyze how these decisions affect the consumer surplus and the performance of the firms. The absence of a market leader leads to higher consumer surplus with the manufacturer investing more in greening. However, cost-sharing may fail if there is no market leader. The retailer has incentive to share the highest proportion of greening costs when it is the leader. When the manufacturer is the leader, the retailer may have incentive to change the cost-sharing proportion over time. Finally, we compare the greening level and learning trajectories for the different scenarios. We provide essential managerial insights on how decisions should be operated, enabling green products to successfully gain a stable market share.
Accès libre
Singularity-free frame fields for line drawing vectorization
Guțan, Olga; Hegde, Shreya; Jimenez Berumen, Erick; Bessmeltsev, Mikhail; Chien, Edward; Université de Montréal. Faculté des arts et des sciences. Département d'informatique et de recherche opérationnelle (Wiley, 2023-07-19)
State-of-the-art methods for line drawing vectorization rely on generated frame fields for robust direction disambiguation, with each of the two axes aligning to different intersecting curve tangents around junctions. However, a common source of topological error for such methods are frame field singularities. To remedy this, we introduce the first frame field optimization framework guaranteed to produce singularity-free fields aligned to a line drawing. We first perform a convex solve for a roughly-aligned orthogonal frame field (cross field), and then comb away its internal singularities with an optimal transport–based matching. The resulting topology of the field is strictly maintained with the machinery of discrete trivial connections in a final, non-convex optimization that allows non-orthogonality of the field, improving smoothness and tangent alignment. Our frame fields can serve as a drop-in replacement for frame field optimizations used in previous work, improving the quality of the final vectorizations.
Accès libre
Differential operators on sketches via alpha contours
Myronova, Mariia; Neveu, William; Bessmeltsev, Mikhail; Université de Montréal. Faculté des arts et des sciences. Département d'informatique et de recherche opérationnelle (Association for Computing Machinery, 2023-08)
A vector sketch is a popular and natural geometry representation depicting a 2D shape. When viewed from afar, the disconnected vector strokes of a sketch and the empty space around them visually merge into positive space and negative space, respectively. Positive and negative spaces are the key elements in the composition of a sketch and define what we perceive as the shape. Nevertheless, the notion of positive or negative space is mathematically ambiguous: While the strokes unambiguously indicate the interior or boundary of a 2D shape, the empty space may or may not belong to the shape’s exterior. For standard discrete geometry representations, such as meshes or point clouds, some of the most robust pipelines rely on discretizations of differential operators, such as Laplace-Beltrami. Such discretizations are not available for vector sketches; defining them may enable numerous applications of classical methods on vector sketches. However, to do so, one needs to define the positive space of a vector sketch, or the sketch shape. Even though extracting this 2D sketch shape is mathematically ambiguous, we propose a robust algorithm, Alpha Contours, constructing its conservative estimate: a 2D shape containing all the input strokes, which lie in its interior or on its boundary, and aligning tightly to a sketch. This allows us to define popular differential operators on vector sketches, such as Laplacian and Steklov operators. We demonstrate that our construction enables robust tools for vector sketches, such as As-Rigid-As-Possible sketch deformation and functional maps between sketches, as well as solving partial differential equations on a vector sketch.
Accès libre
The load planning and sequencing problem for double-stack trains
Ruf, Mortiz; Cordeau, Jean-François; Frejinger, Emma; Université de Montréal. Faculté des arts et des sciences. Département d'informatique et de recherche opérationnelle (Elsevier, 2022-07-21)
This paper addresses the integrated load planning and sequencing problem (LPSP) for double-stack trains. This decision problem occurs in intermodal terminals and consists in assigning containers from a storage area to slots on railcars of outbound trains and in determining the loading sequence of the handling equipment. Even though this a relevant operational problem, it has seen no attention in the operations research literature so far. Prior models either focus on single-stack railcars or treat the load planning and sequencing separately. By extending prior work on load planning, we propose four integer linear programming formulations differing in the number of constraints and variables. An extensive numerical study identifies two formulations that perform best in our setting with respect to the number of optimal solutions found in a given time limit and average solution time. With these formulations, we solve instances with up to 50 containers with a commercial general-purpose solver in less than 20 minutes. A case study based on real data provided by the Canadian National Railway Company highlights that the LPSP can reduce the number of container handlings in intermodal terminals compared to sequential solutions by on average 11.3% and 16.5% for gantry cranes and reach stackers, respectively.
Accès libre
Keypoint-driven line drawing vectorization via polyvector flow
Puhachov, Ivan; Neveu, William; Chien, Edward; Bessmeltsev, Mikhail; Université de Montréal. Faculté des arts et des sciences. Département d'informatique et de recherche opérationnelle (Association for Computing Machinery, 2021-12)
Line drawing vectorization is a daily task in graphic design, computer animation, and engineering, necessary to convert raster images to a set of curves for editing and geometry processing. Despite recent progress in the area, automatic vectorization tools often produce spurious branches or incorrect connectivity around curve junctions; or smooth out sharp corners. These issues detract from the use of such vectorization tools, both from an aesthetic viewpoint and for feasibility of downstream applications (e.g., automatic coloring or inbetweening). We address these problems by introducing a novel line drawing vectorization algorithm that splits the task into three components: (1) finding keypoints, i.e., curve endpoints, junctions, and sharp corners; (2) extracting drawing topology, i.e., finding connections between keypoints; and (3) computing the geometry of those connections. We compute the optimal geometry of the connecting curves via a novel geometric flow — PolyVector Flow — that aligns the curves to the drawing, disambiguating directions around Y-, X-, and T-junctions. We show that our system robustly infers both the geometry and topology of detailed complex drawings. We validate our system both quantitatively and qualitatively, demonstrating that our method visually outperforms previous work.
Accès libre
Probe-level linear model fitting and mixture modeling results in high accuracy detection of differential gene expression
Lemieux, Sébastien; Université de Montréal. Faculté des arts et des sciences. Département d'informatique et de recherche opérationnelle (2006)
BACKGROUND:The identification of differentially expressed genes (DEGs) from Affymetrix GeneChips arrays is currently done by first computing expression levels from the low-level probe intensities, then deriving significance by comparing these expression levels between conditions. The proposed PL-LM (Probe-Level Linear Model) method implements a linear model applied on the probe-level data to directly estimate the treatment effect. A finite mixture of Gaussian components is then used to identify DEGs using the coefficients estimated by the linear model. This approach can readily be applied to experimental design with or without replication.RESULTS:On a wholly defined dataset, the PL-LM method was able to identify 75% of the differentially expressed genes within 10% of false positives. This accuracy was achieved both using the three replicates per conditions available in the dataset and using only one replicate per condition.CONCLUSION:The method achieves, on this dataset, a higher accuracy than the best set of tools identified by the authors of the dataset, and does so using only one replicate per condition.

Parcourir

Dépôts récents