Chance-Constrained Multiple-Choice Knapsack Problem: Model, Algorithms, and Applications.

The multiple-choice knapsack problem (MCKP) is a classic NP-hard combinatorial optimization problem. Motivated by several significant real-world applications, this work investigates a novel variant of MCKP called the chance-constrained MCKP (CCMCKP), where item weights are random variables. In particular, we focus on the practical scenario of CCMCKP, in which the probability distributions of random weights are unknown and only sample data is available. We first present the problem formulation of CCMCKP and then establish the two benchmark sets. The first set contains synthetic instances, while the second set is designed to simulate a real-world application scenario of a telecommunication company. To solve CCMCKP, we propose a data-driven adaptive local search (DDALS) algorithm. Compared to existing stochastic optimization and distributionally robust optimization methods, the main novelty of DDALS lies in its data-driven solution evaluation approach, which does not make any assumptions about the underlying distributions and is highly effective even when faced with a high intensity of the chance constraint and a limited amount of sample data. Experimental results demonstrate the superiority of DDALS over the baselines on both the benchmarks. Finally, DDALS can serve as the baseline for future research, and the benchmark sets are open-sourced to further promote research on this challenging problem.

Enantioselective Ir-Catalyzed Allyl Alkylation/Semipinacol Rearrangement.

The semipinacol rearrangement is a powerful and versatile method for constructing all-carbon quaternary stereocenters. The development of catalytic asymmetric semipinacol rearrangements using multifunctionalizable electrophiles remains highly sought-after in organic synthesis. In this study, a catalytic enantioselective allylic cation-induced semipinacol rearrangement reaction was presented that enables the simultaneous construction of two skipped chiral carbon centers. Chiral Ir(I)-(P,olefin) and Sc(OTf)3 catalysts cooperatively initiate the asymmetric allylic alkylation of alkenyl cyclobutanols with allylic alcohols, triggering ring expansion of the cyclobutanol moiety through a stereoselective 1,2-alkyl migration. The reaction afforded a range of cyclopentanones bearing an α-quaternary carbon that is adjacent to a chiral allyl scaffold. The products were applied to synthesize enantioenriched fused tricyclopentanoids bearing four stereogenic carbon centers.