🤖 machine learning

Hard Rules, Soft Preferences: Bridging Reasoning, Learning, and Optimization for Personalized Packing Checklist Generation

This paper proposes a three-stage reasoning-guided learning framework that integrates a symbolic engine, a preference learner, and a CP-SAT optimizer to generate personalized, regulation-compliant packing checklists, significantly outperforming existing LLMs and greedy methods in accuracy and constraint satisfaction while demonstrating real-world efficacy in a production travel app.

Original authors: Himel Dev, Madhusudan Basak, Tanmoy Sen, Paromita Shome, Bashima Islam

Published 2026-07-20

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Himel Dev, Madhusudan Basak, Tanmoy Sen, Paromita Shome, Bashima Islam

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to build the perfect playlist for a road trip. You want songs that fit the mood, but you also have a hard limit: your phone's battery might die if you stream too much, and you can't play a heavy metal song if your grandma is in the car. This is the daily struggle of "constrained personalization." In the world of computer science, this is a tricky puzzle where a machine must learn what you like (your soft preferences) while obeying a strict set of unbreakable laws (hard rules), like safety regulations or physical space limits. Usually, computers are great at guessing what you like, but terrible at following strict rules, or vice versa. They might suggest a song you love, but forget that it's too long for your battery, or they might follow the rules so strictly that the playlist is boring. The big question scientists have been asking is: How do we build a system that is both a fun, personal DJ and a strict, rule-following bouncer at the same time?

This paper introduces a clever three-step "brain" designed to solve exactly that problem, specifically for packing your suitcase for a plane trip. The authors, working with a travel app called FlyEnJoy, realized that existing packing assistants were either too generic (giving everyone the same list) or too risky (suggesting items that might get you stopped at security). To fix this, they built a system that acts like a team of three specialists working in a relay race.

First, there's the Rulebook Robot. Before thinking about what you like, this stage uses a massive, human-written list of 226 rules to generate a "seed" checklist. It's like a super-cautious friend who knows every TSA regulation, safety rule, and travel dependency (like "if you pack a camera, you must pack a charger"). This robot doesn't worry about your personal style; it just makes sure the list is safe, legal, and complete. It creates a huge list of 49 items on average, ensuring that nothing essential is missed, even if you've never traveled before.

Next, the Taste-Maker steps in. This is where the machine learning happens. The system looks at how real people edit those huge, safe lists. Did they throw away the heavy winter coat for a beach trip? Did they add a specific type of hiking boot? The system learns two things separately: first, whether an item should be in the bag at all (inclusion), and second, how important it is compared to other items (ranking). By splitting these tasks, the system avoids a common trap called "survivorship bias," where it might think an item is great just because it survived the editing process, ignoring the fact that many people might have deleted it entirely. This stage learns your personal style with high accuracy, acting like a smart stylist who knows exactly what you prefer.

Finally, the Optimizer takes the stage. This is the math wizard. It takes the personalized list from the Taste-Maker and the strict rules from the Rulebook Robot and solves a complex puzzle. It has to fit your favorite items into your bags without breaking the weight limit, violating liquid rules, or separating items that need to stay together (like a camera and its lens). It uses a powerful math tool called CP-SAT to find the perfect combination. Unlike other methods that just guess and check (which often fail), this optimizer guarantees that 100% of the time, the final list is physically possible and legally compliant.

The results are impressive. When tested on 604 different trip scenarios, the Rulebook Robot remembered 99.7% of the items people actually wanted. The Taste-Maker learned to predict what people would keep with 94.3% accuracy. Most importantly, the Optimizer succeeded in packing everything perfectly every single time, whereas simpler methods failed to follow the rules 72% of the time. When this system was deployed in a real travel app, users finished their packing lists twice as fast and made fewer edits, proving that this mix of strict rules and smart learning actually works in the real world. The paper suggests that this three-part team approach could be used for other tricky problems where safety and personal taste collide, like planning a hospital discharge or organizing immigration paperwork, but for now, it's just making sure you don't forget your toothbrush or get stopped at security.

Technical Summary: Hard Rules, Soft Preferences

Problem Formulation

The paper addresses the challenge of generating personalized packing checklists for air travel, a task characterized by the tension between hard feasibility constraints and sparse, context-dependent user preferences. Travelers must adhere to non-negotiable regulatory (e.g., TSA/FAA), safety, capacity, and item-dependency constraints while adapting to specific trip contexts (destination, duration, activities).

Existing solutions fall into two inadequate categories:

Template-driven systems: These are generic, ignore context (e.g., weather, specific activities), and fail to handle inter-item dependencies or regulatory nuances.
Unconstrained recommenders (including LLMs): While capable of personalization, they cannot guarantee feasibility. They often violate safety rules (e.g., suggesting prohibited liquids) or fail to respect capacity limits. Furthermore, standard learning approaches suffer from survivorship bias when trained on implicit feedback (e.g., items kept in a list vs. items removed), as ranking labels are only observed for retained items.

The core objective is to generate a checklist $S$ that maximizes predicted traveler utility $U(S|c)$ subject to a set of hard constraints $R$ , ensuring the output is both compliant and personalized.

Methodology

The authors propose a reasoning-guided learning framework consisting of three distinct stages that bridge symbolic reasoning, machine learning, and constrained optimization.

Stage 1: Symbolic Reasoning (Compliance and Recall)

To ensure feasibility and handle cold-start scenarios (where user history is sparse), the system employs a symbolic inference engine.

Knowledge Base: Encodes 226 declarative rules across 378 atomic items and 103 pre-trip tasks. Rules are categorized by priority: Regulatory and Wellbeing rules (high priority) are evaluated before Contextual, Activity, and Traveler-specific rules.
Inference Mechanism: Uses priority-based forward chaining. Starting from enriched trip context (e.g., destination, duration, special needs), the engine fires rules to emit item candidates and new facts (e.g., inferring "requires_adapter" from "international_trip").
Output: A high-recall, regulation-compliant "seed checklist." This stage prioritizes recall (capturing all potentially relevant items) over precision, deliberately over-generating candidates to be filtered in later stages.

Stage 2: Preference Learning (Personalization and Precision)

This stage learns soft personalization signals from user edit logs to filter the seed checklist and rank items, specifically addressing survivorship bias.

Two-Stage Modeling: The authors decompose the problem into two coupled subproblems:
1. Inclusion (Binary): Predicts whether an item suggested by the symbolic engine should be kept or removed. This is modeled using Gradient Boosted Trees (GBM) to predict inclusion probability $p_{include}$ .
2. Ranking (Relative): Predicts the priority order among items that are retained. This is modeled using LambdaMART (Learning to Rank) to optimize NDCG metrics.
Bias Mitigation: By separating inclusion from ranking, the model avoids overestimating the utility of items that are frequently removed by users (which would otherwise be absent from pairwise ranking comparisons).
Feature Engineering: Models utilize symbolic provenance features (e.g., which rule triggered the item, rule priority) alongside trip context, allowing the system to learn from sparse interaction data.
Utility Construction: The final utility score for an item is a multiplicative composition of the learned inclusion probability, the learned ranking score, and a symbolic prior that enforces high utility for safety-critical items regardless of learned preferences.

Stage 3: Constrained Optimization (Feasibility and Utility)

The final stage selects a subset of items and assigns them to specific bags (carry-on, checked, personal item) using a CP-SAT (Constraint Programming with SAT) solver.

Objective: Maximize expected retained utility while minimizing expected monetary loss (accounting for bag loss probabilities).
Constraints: The solver enforces hard constraints including:
- Physical: Weight and volume capacity limits.
- Regulatory: TSA/FAA eligibility (e.g., lithium batteries in carry-on only).
- Environmental: Temperature sensitivity (e.g., insulin).
- Dependencies: "Must-together" (e.g., camera body + lens) and "must-separate" (e.g., liquids + electronics) constraints.
Risk Awareness: The objective function penalizes placing high-value items in high-risk bags (e.g., checked luggage).

Key Contributions

Constraint-Aware Candidate Generation: A symbolic engine achieving 99.7% recall and 0.96 rubric validity, significantly outperforming frontier LLMs (0.78–0.81) on regulatory and safety compliance.
Survivorship-Bias-Aware Preference Learning: A two-stage formulation (Inclusion + Ranking) that achieves an AUC-ROC of 0.943 for inclusion and NDCG@5 of 0.923 for ranking, effectively mitigating bias in implicit feedback.
By-Construction Feasibility: A CP-SAT formulation that guarantees 100% constraint satisfaction, compared to 28% for greedy heuristics and 10% for random baselines.
General Design Pattern: The architecture demonstrates a reusable pattern for constrained personalization where hard feasibility coexists with sparse preference signals, applicable beyond travel (e.g., clinical discharge planning).

Experimental Results

The framework was evaluated on 604 labeled trip scenarios containing 29,000 inclusion labels and 343,000 pairwise comparisons.

Symbolic Engine: Achieved near-perfect recall (99.7%) across all trip durations. Precision was moderate (54–83%) by design, as the seed is intentionally over-generated.
Preference Models: The GBM inclusion model and LambdaMART ranking model outperformed baselines (Logistic Regression, Random Forest, Neural Collaborative Filtering). Symbolic provenance features were identified as the strongest predictors.
Optimization: The CP-SAT solver satisfied all constraints (0 violations), whereas greedy and random methods failed significantly on dependency constraints (e.g., separating liquids from electronics).
End-to-End Performance: The pipeline achieved 80.9% precision and 34.5% recall against a human reference checklist. The recall is bounded by the physical capacity of the luggage (packing ~14 items vs. a human reference of ~32), meaning the system recovers roughly 80% of the oracle-feasible maximum.
LLM Comparison: The symbolic engine scored 0.96 on a validity rubric (TSA compliance, weather, activity, completeness), substantially beating GPT-5 (0.78), Claude Opus 4.5 (0.80), and Gemini 3 Pro (0.81).

Real-World Deployment

The system was deployed in FlyEnJoy, a production iOS travel app running entirely on-device.

Impact: Checklist initiations increased by 200%, and completed checklists increased by 100%.
Efficiency: Time per session decreased by 49.6%, driven by a reduction in manual editing (fewer add/remove actions required).
Significance: The deployment confirmed that the framework delivers measurable real-world value over a static, template-based baseline, successfully balancing strict regulatory compliance with personalized utility.

Significance and Limitations

The paper argues that the primary value of this work lies in its hybrid architecture, which reconciles the interpretability and robustness of symbolic reasoning with the adaptability of machine learning and the rigor of constraint optimization. It demonstrates that for safety-critical, constrained domains, "soft" learning alone is insufficient; hard rules must be encoded symbolically and enforced via optimization.

The authors note a principal limitation: the cost of authoring and maintaining domain rules. However, they suggest that rule reuse across families and the generalizability of the three-stage pattern to other domains (like immigration documentation) serve as mitigations and directions for future work. The paper does not claim to solve the general packing problem for all scenarios but specifically targets the intersection of air travel regulations and personalization.