Marouane Ibn Brahim

Papers

Journal Articles

• Maximum load assortment optimization: Approximation algorithms and adaptivity gaps
  with Omar El Housni and Danny Segev.
  Operations Research, Vol. 74, No. 1, pp. 408–429, 2025.
  • ★Finalist, INFORMS George Nicholson Student Paper Competition, 2025
  Abstract

  Motivated by modern-day applications such as attended home delivery and preference-based group scheduling, where decision makers wish to steer a large number of customers toward choosing the exact same alternative, we introduce a novel class of assortment optimization problems, referred to as maximum load assortment optimization. In such settings, given a universe of substitutable products, we are facing a stream of customers, each choosing between either selecting a product out of an offered assortment or opting to leave without making a selection. Assuming that these decisions are governed by the multinomial logit choice model, we define the random load of any underlying product as the total number of customers who select it. Our objective is to offer an assortment of products to each customer so that the expected maximum load across all products is maximized.

  We consider both static and dynamic formulations of the maximum load assortment optimization problem. In the static setting, a single offer set is carried throughout the entire process of customer arrivals, whereas in the dynamic setting, the decision maker offers a personalized assortment to each customer, based on the entire information available at that time. As can only be expected, both formulations present a wide range of computational challenges and analytical questions. The main contribution of this paper resides in proposing efficient algorithmic approaches for computing near-optimal static and dynamic assortment policies. In particular, we develop a polynomial time approximation scheme for the static problem formulation. Additionally, we demonstrate that an elegant policy utilizing weight-ordered assortments yields a 1/2 approximation. Concurrently, we prove that such policies are sufficiently strong to provide a 1/4 approximation with respect to the dynamic formulation, establishing a constant factor bound on its adaptivity gap. Finally, we design an adaptive policy whose expected maximum load is within factor 1 - ε of optimal, admitting a quasi-polynomial time implementation.

• Assortment optimization with visibility constraints
  with Théo Barré, Omar El Housni, Andrea Lodi and Danny Segev.
  Mathematical Programming, Vol. 216, No. 1, pp. 177–220, 2026.
  • ★Selected for presentation, M&SOM Supply Chain Management SIG, 2024
  Abstract

  Motivated by applications in e-retail and online advertising, we study the problem of assortment optimization under visibility constraints (APV). Here, we are given a universe of substitutable products and a stream of customers. The objective is to determine the optimal assortment of products to offer to each customer in order to maximize the total expected revenue, subject to exogenously-given visibility constraints, stating that each product should be shown to a minimum number of customers. We assume that customer choices follow a Multinomial Logit model (MNL). We provide a structural characterization of optimal assortments and present a linear time algorithm for solving APV. To this end, we introduce a novel function called the "expanded revenue" of an assortment and establish its supermodularity; our algorithm takes advantage of this structural property. Additionally, we prove that APV can be formulated as a compact linear program.

  Next, we consider APV with cardinality constraints, which limit the maximum number of products that can be included in an assortment. We prove this problem to be strongly NP-hard and not admitting a Fully Polynomial Time Approximation Scheme (FPTAS), even when all products have identical prices. Subsequently, we devise a Polynomial Time Approximation Scheme (PTAS) for APV under cardinality constraints with identical prices. We also examine the revenue loss resulting from the enforcement of visibility constraints, comparing it to the unconstrained problem. To offset this loss, we propose a novel strategy to distribute the loss incurred among the products subject to visibility constraints, charging each vendor an amount proportional to their product's contribution to the revenue loss.

• Runtime analysis for permutation-based evolutionary algorithms.
  with Benjamin Doerr and Yassine Ghannane.
  Algorithmica, Vol. 86, pp. 90–129, 2024.
  • Earlier version: Preliminary version appeared in the Proceedings of the Genetic and Evolutionary Computation Conference (GECCO '22)
  Abstract

  While the theoretical analysis of evolutionary algorithms (EAs) has made significant progress for pseudo-Boolean optimization problems in the last 25 years, only sporadic theoretical results exist on how EAs solve permutation-based problems. To overcome the lack of permutation-based benchmark problems, we propose a general way to transfer the classic pseudo-Boolean benchmarks into benchmarks defined on sets of permutations. We then conduct a rigorous runtime analysis of the permutation-based (1+1) EA proposed by Scharnow et al. (J Math Model Algorithm 3:349-366, 2004) on the analogues of the LeadingOnes and Jump benchmarks. The latter shows that, different from bit-strings, it is not only the Hamming distance that determines how difficult it is to mutate a permutation σ into another one τ, but also the precise cycle structure of στ^-1.

  For this reason, we also regard the more symmetric scramble mutation operator. We observe that it not only leads to simpler proofs, but also reduces the runtime on jump functions with odd jump size by a factor of Θ(n). Finally, we show that a heavy-tailed version of the scramble operator, as in the bit-string case, leads to a speed-up of order m^Θ(m) on jump functions with jump size m. A short empirical analysis confirms these findings, but also reveals that small implementation details like the rate of void mutations can make an important difference.

Working Papers

• When is less choice enough? Centralization in multi-item pricing.
  with Omar El Housni.
  Draft available upon request.
  Abstract

  We study the revenue loss from replacing a multi-item price menu by a single item-price offer. Under decentralized pricing, the seller posts item-specific prices and customers choose utility-maximizing items; under centralized pricing, the seller chooses one item and one price. We ask when this restriction preserves revenue, and when it is costly.

  We show that the answer is governed by the geometry of preference heterogeneity. In finite-support markets, centralized revenue can be a factor equal to the number of customer segments below decentralized revenue, and this is tight. The loss is driven by horizontal heterogeneity: different segments prefer different items. By contrast, if all valuation vectors lie on a common nonnegative ray, customers may differ in willingness to pay but agree on relative item values, and centralized and decentralized pricing have the same optimal revenue. With k aligned preference blocks, a centralized offer obtains at least a 1/k fraction of decentralized revenue.

  We prove that this no-gap result is robust to approximate alignment. If a valuation matrix is within entrywise distance ε of the nonnegative rank-one cone, the decentralized revenue advantage is at most O(nε), and this dependence is tight. We also extend the analysis to stochastic environments around a common aligned core and to additive item-level shocks. Overall, centralization can be costly under horizontal heterogeneity, but is revenue-safe when preferences are mostly aligned or vertical.