pith. sign in

arxiv: 2407.02339 · v2 · submitted 2024-07-02 · 🧮 math.OC

Logic-Based Benders Decomposition for Time Slot Management with Mixed Logit Demand

Dorsa Abdolhamidi , Carla Juvin , Virginie Lurkin This is my paper

Pith reviewed 2026-05-23 23:03 UTC · model grok-4.3

classification 🧮 math.OC
keywords logic-based Benders decompositiontime slot managementmixed logit demandattended home deliverysample average approximationvehicle routingstochastic mixed-integer programming
0
0 comments X

The pith

Logic-based Benders decomposition solves the integrated time slot, pricing, and routing problem under mixed logit demand for instances with up to 10 customers.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper develops a logic-based Benders decomposition framework for the choice-based time slot management problem in attended home delivery systems. It jointly optimizes slot offerings, price discounts, and routing decisions while embedding customer choices through sample average approximation of a mixed logit model, which produces a large stochastic mixed-integer program. The decomposition splits strategic assortment and pricing decisions plus choice from scenario-specific vehicle routing subproblems and supplies custom optimality cuts that exploit the routing structure. These elements, together with strengthening strategies such as relaxation-based cut generation and valid inequalities, enable proven optimal solutions on instances that direct mixed-integer linear programming cannot solve. A sympathetic reader would care because the work shows how decomposition can manage the combined difficulty of stochastic demand modeling and operational routing constraints.

Core claim

The authors establish that a logic-based Benders decomposition framework, which separates strategic assortment and pricing decisions together with customer choice from scenario-specific vehicle routing subproblems and derives problem-specific optimality cuts that exploit the routing structure, provides proven optimal solutions for instances with up to 10 customers and consistently tight optimality gaps for instances with 15-20 customers, thereby significantly extending the range of solvable instances compared to direct MILP approaches.

What carries the argument

Logic-based Benders decomposition that separates assortment, pricing, and choice decisions from scenario-specific routing subproblems, using problem-specific optimality cuts derived from the routing structure.

If this is right

  • The framework yields proven optimal solutions for instances with up to 10 customers.
  • It produces consistently tight optimality gaps for instances with 15-20 customers.
  • Relaxation-based cut generation and capacity- and flow-based valid inequalities improve computational performance.
  • For larger instances the approach still supplies meaningful upper bounds.
  • The results demonstrate the interaction between stochastic choice modeling, routing complexity, and decomposition design.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same cut-generation strategy could be tested on other integrated assortment and routing problems that combine discrete choice with vehicle operations.
  • Increasing the number of scenarios in the sample average approximation on the same benchmark set would reveal how sensitive the reported solutions are to demand sampling.
  • If computation times drop further, the method could support repeated re-optimization of offered slots as new customer arrivals are observed during a booking horizon.
  • Replacing the mixed logit choice model with a simpler multinomial logit version on identical instances would isolate how much extra computational cost the richer demand model imposes.

Load-bearing premise

The problem-specific optimality cuts derived from the routing structure are valid and sufficiently strong, and the sample average approximation with the chosen scenarios adequately represents the underlying mixed logit demand for the tested instances.

What would settle it

Solving an instance with a commercial MILP solver on the full model and obtaining a different objective value or feasible solution than the decomposition reports would show that the cuts are invalid or that the approximation does not match the demand model.

read the original abstract

This paper develops an exact solution framework for the choice-based time slot management problem under mixed logit demand in attended home delivery systems. The problem jointly optimizes delivery slot offerings, price discounts, and routing decisions, with customer choices endogenously modeled through a simulation-based mixed logit formulation embedded via sample average approximation, resulting in a large-scale stochastic mixed-integer program. To address this complexity, we propose a logic-based Benders decomposition (LBBD) that separates strategic assortment and pricing decisions, together with customer choice, from scenario-specific vehicle routing subproblems. We derive problem-specific optimality cuts that exploit the routing structure to provide stronger bounds than generic cuts, and establish their validity. To enhance computational performance, we introduce and systematically evaluate several strengthening strategies, including relaxation-based cut generation and capacity- and flow-based valid inequalities. Computational experiments on benchmark instances show that the proposed framework significantly extends the range of solvable instances compared to direct MILP approaches. The method yields proven optimal solutions for instances with up to 10 customers and consistently tight optimality gaps for instances with 15-20 customers. For larger instances, the approach provides meaningful upper bounds, while remaining computationally challenging for larger problem sizes. Overall, the results highlight the interaction between stochastic choice modeling, routing complexity, and decomposition design, and demonstrate the potential of LBBD for solving integrated choice-based optimization problems.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

3 major / 2 minor

Summary. The paper develops a logic-based Benders decomposition (LBBD) framework for the choice-based time slot management problem with mixed logit demand in attended home delivery. It formulates the problem as a large-scale stochastic MIP via sample average approximation (SAA) of the mixed logit choice probabilities, then decomposes strategic assortment/pricing/choice decisions from scenario-specific vehicle routing subproblems. Problem-specific optimality cuts exploiting the routing structure are derived and claimed to be valid, with additional strengthening via relaxation-based cut generation and valid inequalities. Computational results on benchmark instances show the method solves instances with up to 10 customers to optimality and yields tight gaps for 15-20 customers, outperforming direct MILP.

Significance. If the validity of the problem-specific cuts holds in the presence of endogenous SAA choice probabilities, the work provides a concrete algorithmic advance for integrated assortment, pricing, and routing problems under discrete choice models. These problems arise in e-commerce logistics and are typically intractable at realistic sizes; an exact method that scales to 20 customers with proven optimality or tight bounds would be a useful benchmark. The explicit use of LBBD with routing-exploiting cuts and systematic strengthening strategies is a methodological strength.

major comments (3)
  1. [§4.2–4.3] §4.2–4.3 (Optimality cuts): The central claim that the LBBD optimality cuts remain valid once the master problem encodes the SAA approximation of mixed-logit probabilities (which are endogenous to the assortment and pricing decisions) requires explicit verification. The skeptic note correctly identifies this as the least-secured step; the manuscript must show whether the cuts are scenario-wise or expectation-based and how they correctly propagate the logit probabilities without assuming fixed demand.
  2. [§5] §5 (Computational experiments): The reported optimality gaps for 15–20 customer instances are for the SAA problem; it is unclear how many scenarios are used, how the scenario set is generated, and whether the gaps remain meaningful when the SAA approximation error is taken into account. This directly affects the claim that the method “significantly extends the range of solvable instances.”
  3. [Table 2 / §5.2] Table 2 / §5.2: The comparison against “direct MILP” should report both the number of instances solved to proven optimality and the wall-clock time distribution; without these, the headline claim that LBBD yields proven optima up to 10 customers is difficult to assess for robustness.
minor comments (2)
  1. Notation for the mixed-logit probabilities and the SAA objective should be introduced once and used consistently; the current alternation between p_{ik} and the approximated expectation is occasionally ambiguous.
  2. The abstract states that validity of the cuts is established, but the main text should include a short self-contained proof sketch or reference to the precise theorem number rather than a high-level assertion.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the thorough review and valuable comments on our manuscript. We address each major comment below and indicate the revisions we will make to strengthen the paper.

read point-by-point responses

  1. Referee: [§4.2–4.3] §4.2–4.3 (Optimality cuts): The central claim that the LBBD optimality cuts remain valid once the master problem encodes the SAA approximation of mixed-logit probabilities (which are endogenous to the assortment and pricing decisions) requires explicit verification. The skeptic note correctly identifies this as the least-secured step; the manuscript must show whether the cuts are scenario-wise or expectation-based and how they correctly propagate the logit probabilities without assuming fixed demand.

    Authors: The optimality cuts are scenario-wise: each cut is derived from the optimal solution of a scenario-specific routing subproblem after the master has fixed the assortment, pricing, and resulting SAA choice probabilities. Because the master objective is the probability-weighted sum of the scenario routing costs, a valid lower bound on any individual scenario cost remains a valid lower bound on the overall objective; the cuts therefore do not rely on fixed (exogenous) demand. We will add an explicit paragraph in §4.2 that states this argument formally and clarifies the distinction between scenario-wise and expectation-based cuts. revision: partial

  2. Referee: [§5] §5 (Computational experiments): The reported optimality gaps for 15–20 customer instances are for the SAA problem; it is unclear how many scenarios are used, how the scenario set is generated, and whether the gaps remain meaningful when the SAA approximation error is taken into account. This directly affects the claim that the method “significantly extends the range of solvable instances.”

    Authors: We agree that these details are necessary for a complete assessment. In the revised §5 we will report the exact number of scenarios employed, describe their Monte-Carlo generation from the mixed-logit distribution, and add a short discussion noting that the reported gaps pertain to the SAA problem (standard practice) while out-of-sample validation of the SAA error can be performed separately. This clarification will be added without altering the computational claims. revision: yes

  3. Referee: [Table 2 / §5.2] Table 2 / §5.2: The comparison against “direct MILP” should report both the number of instances solved to proven optimality and the wall-clock time distribution; without these, the headline claim that LBBD yields proven optima up to 10 customers is difficult to assess for robustness.

    Authors: We will revise Table 2 and the accompanying text in §5.2 to include, for each method and instance size, the number of instances solved to proven optimality within the time limit, together with summary statistics (mean, median, minimum, maximum) of the wall-clock times. This additional information will make the robustness of the “up to 10 customers” claim transparent. revision: yes

Circularity Check

0 steps flagged

No circularity in LBBD derivation or cut validity claims

full rationale

The paper develops an LBBD algorithm separating assortment/pricing/choice decisions from routing subproblems, derives problem-specific optimality cuts, and states that their validity is established. No quoted equations or steps reduce the claimed results to fitted parameters, self-definitions, or unverified self-citations. The derivation chain consists of standard decomposition techniques plus structure-exploiting cuts whose validity is asserted as proven within the work, making the framework self-contained against external benchmarks. The reader's score of 1.0 is consistent with at most a minor non-load-bearing citation not visible here.

Axiom & Free-Parameter Ledger

1 free parameters · 1 axioms · 0 invented entities

The central claim depends on the validity of the derived optimality cuts and the quality of the SAA approximation to the mixed logit model; the number of scenarios is a key modeling choice.

free parameters (1)
  • Number of scenarios in SAA
    The sample size chosen for the sample average approximation that embeds the mixed logit demand into the MIP.
axioms (1)
  • domain assumption Customer choices are accurately represented by the mixed logit model
    The demand is endogenously modeled through a simulation-based mixed logit formulation.

pith-pipeline@v0.9.0 · 5776 in / 1218 out tokens · 23627 ms · 2026-05-23T23:03:41.869707+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.