Split MPP by maximizing expected delivered amount (#2792)

diff --git a/docs/release-notes/eclair-vnext.md b/docs/release-notes/eclair-vnext.md
index ddd4e53..c590cf5 100644
--- a/docs/release-notes/eclair-vnext.md
+++ b/docs/release-notes/eclair-vnext.md
@@ -4,7 +4,14 @@
 
 ## Major changes
 
-<insert changes>
+### New MPP splitting strategy
+
+Eclair can send large payments using multiple low-capacity routes by sending as much as it can through each route (if `randomize-route-selection = false`) or some random fraction (if `randomize-route-selection = true`).
+These splitting strategies are now specified using `mpp.splitting-strategy = "full-capacity"` or `mpp.splitting-strategy = "randomize"`.
+In addition, a new strategy is available: `mpp.splitting-strategy = "max-expected-amount"` will send through each route the amount that maximizes the expected delivered amount (amount sent multiplied by the success probability).
+
+Eclair's path-finding algorithm can be customized by modifying the `eclair.router.path-finding.experiments.*` sections of your `eclair.conf`.
+The new `mpp.splitting-strategy` goes in these sections, or in `eclair.router.path-finding.default` from which they inherit.
 
 ### Remove support for legacy channel codecs
 
diff --git a/eclair-core/src/main/resources/reference.conf b/eclair-core/src/main/resources/reference.conf
index 55a1041..a6c7b83 100644
--- a/eclair-core/src/main/resources/reference.conf
+++ b/eclair-core/src/main/resources/reference.conf
@@ -461,6 +461,7 @@ eclair {
         mpp {
           min-amount-satoshis = 15000 // minimum amount sent via partial HTLCs
           max-parts = 5 // maximum number of HTLCs sent per payment: increasing this value will impact performance
+          splitting-strategy = "randomize" // Can be either "full-capacity", "randomize" or "max-expected-amount"
         }
 
         boundaries {
diff --git a/eclair-core/src/main/scala/fr/acinq/eclair/NodeParams.scala b/eclair-core/src/main/scala/fr/acinq/eclair/NodeParams.scala
index 733155b..e824e68 100644
--- a/eclair-core/src/main/scala/fr/acinq/eclair/NodeParams.scala
+++ b/eclair-core/src/main/scala/fr/acinq/eclair/NodeParams.scala
@@ -468,7 +468,12 @@ object NodeParams extends Logging {
         usePastRelaysData = config.getBoolean("use-past-relay-data")),
       mpp = MultiPartParams(
         Satoshi(config.getLong("mpp.min-amount-satoshis")).toMilliSatoshi,
-        config.getInt("mpp.max-parts")),
+        config.getInt("mpp.max-parts"),
+        config.getString("mpp.splitting-strategy") match {
+          case "full-capacity" => MultiPartParams.FullCapacity
+          case "randomize" => MultiPartParams.Randomize
+          case "max-expected-amount" => MultiPartParams.MaxExpectedAmount
+        }),
       experimentName = name,
       experimentPercentage = config.getInt("percentage"))
 
diff --git a/eclair-core/src/main/scala/fr/acinq/eclair/payment/send/MultiPartPaymentLifecycle.scala b/eclair-core/src/main/scala/fr/acinq/eclair/payment/send/MultiPartPaymentLifecycle.scala
index 0f225a4..b486e22 100644
--- a/eclair-core/src/main/scala/fr/acinq/eclair/payment/send/MultiPartPaymentLifecycle.scala
+++ b/eclair-core/src/main/scala/fr/acinq/eclair/payment/send/MultiPartPaymentLifecycle.scala
@@ -27,6 +27,7 @@ import fr.acinq.eclair.payment.PaymentSent.PartialPayment
 import fr.acinq.eclair.payment._
 import fr.acinq.eclair.payment.send.PaymentInitiator.SendPaymentConfig
 import fr.acinq.eclair.payment.send.PaymentLifecycle.SendPaymentToRoute
+import fr.acinq.eclair.router.Router.MultiPartParams.FullCapacity
 import fr.acinq.eclair.router.Router._
 import fr.acinq.eclair.{FSMDiagnosticActorLogging, Logs, MilliSatoshiLong, NodeParams, TimestampMilli}
 import scodec.bits.ByteVector
@@ -57,7 +58,7 @@ class MultiPartPaymentLifecycle(nodeParams: NodeParams, cfg: SendPaymentConfig,
 
   when(WAIT_FOR_PAYMENT_REQUEST) {
     case Event(r: SendMultiPartPayment, _) =>
-      val routeParams = r.routeParams.copy(randomize = false) // we don't randomize the first attempt, regardless of configuration choices
+      val routeParams = r.routeParams.copy(randomize = false, mpp = r.routeParams.mpp.copy(splittingStrategy = FullCapacity)) // we don't randomize the first attempt, regardless of configuration choices
       log.debug("sending {} with maximum fee {}", r.recipient.totalAmount, r.routeParams.getMaxFee(r.recipient.totalAmount))
       val d = PaymentProgress(r, r.maxAttempts, Map.empty, Ignore.empty, retryRouteRequest = false, failures = Nil)
       router ! createRouteRequest(self, nodeParams, routeParams, d, cfg)
diff --git a/eclair-core/src/main/scala/fr/acinq/eclair/remote/EclairInternalsSerializer.scala b/eclair-core/src/main/scala/fr/acinq/eclair/remote/EclairInternalsSerializer.scala
index 10336d0..305b141 100644
--- a/eclair-core/src/main/scala/fr/acinq/eclair/remote/EclairInternalsSerializer.scala
+++ b/eclair-core/src/main/scala/fr/acinq/eclair/remote/EclairInternalsSerializer.scala
@@ -64,13 +64,17 @@ object EclairInternalsSerializer {
       ("useLogProbability" | bool(8)) ::
       ("usePastRelaysData" | bool(8))).as[HeuristicsConstants]
 
-  val weightRatiosCodec: Codec[WeightRatios[PaymentPathWeight]] =
-    discriminated[WeightRatios[PaymentPathWeight]].by(uint8)
+  val weightRatiosCodec: Codec[HeuristicsConstants] =
+    discriminated[HeuristicsConstants].by(uint8)
       .typecase(0xff, heuristicsConstantsCodec)
 
   val multiPartParamsCodec: Codec[MultiPartParams] = (
     ("minPartAmount" | millisatoshi) ::
-      ("maxParts" | int32)).as[MultiPartParams]
+      ("maxParts" | int32) ::
+      ("splittingStrategy" | discriminated[MultiPartParams.SplittingStrategy].by(uint8)
+        .typecase(0, provide(MultiPartParams.FullCapacity))
+        .typecase(1, provide(MultiPartParams.Randomize))
+        .typecase(2, provide(MultiPartParams.MaxExpectedAmount)))).as[MultiPartParams]
 
   val pathFindingConfCodec: Codec[PathFindingConf] = (
     ("randomize" | bool(8)) ::
diff --git a/eclair-core/src/main/scala/fr/acinq/eclair/router/BalanceEstimate.scala b/eclair-core/src/main/scala/fr/acinq/eclair/router/BalanceEstimate.scala
index 7a492e2..f59a003 100644
--- a/eclair-core/src/main/scala/fr/acinq/eclair/router/BalanceEstimate.scala
+++ b/eclair-core/src/main/scala/fr/acinq/eclair/router/BalanceEstimate.scala
@@ -216,7 +216,7 @@ case class BalanceEstimate private(low: MilliSatoshi,
    * - probability that it can relay a payment of high is decay(high, 0, highTimestamp) which is close to 0 if highTimestamp is recent
    * - probability that it can relay a payment of maxCapacity is 0
    */
-  def canSend(amount: MilliSatoshi, now: TimestampSecond): Double = {
+  def canSendAndDerivative(amount: MilliSatoshi, now: TimestampSecond): (Double, Double) = {
     val a = amount.toLong.toDouble
     val l = low.toLong.toDouble
     val h = high.toLong.toDouble
@@ -227,15 +227,17 @@ case class BalanceEstimate private(low: MilliSatoshi,
     val pHigh = decay(high, 0, highTimestamp, now)
 
     if (amount < low) {
-      (l - a * (1.0 - pLow)) / l
+      ((l - a * (1.0 - pLow)) / l, (pLow - 1.0) / l)
     } else if (amount < high) {
-      ((h - a) * pLow + (a - l) * pHigh) / (h - l)
+      (((h - a) * pLow + (a - l) * pHigh) / (h - l), (pHigh - pLow) / (h - l))
     } else if (h < c) {
-      ((c - a) * pHigh) / (c - h)
+      (((c - a) * pHigh) / (c - h), (-pHigh) / (c - h))
     } else {
-      0
+      (0.0, 0.0)
     }
   }
+
+  def canSend(amount: MilliSatoshi, now: TimestampSecond): Double = canSendAndDerivative(amount, now)._1
 }
 
 object BalanceEstimate {
diff --git a/eclair-core/src/main/scala/fr/acinq/eclair/router/Graph.scala b/eclair-core/src/main/scala/fr/acinq/eclair/router/Graph.scala
index 822e163..13d98e2 100644
--- a/eclair-core/src/main/scala/fr/acinq/eclair/router/Graph.scala
+++ b/eclair-core/src/main/scala/fr/acinq/eclair/router/Graph.scala
@@ -501,13 +501,6 @@ object Graph {
      * @param balance_opt (optional) available balance that can be sent through this edge
      */
     case class GraphEdge private(desc: ChannelDesc, params: HopRelayParams, capacity: Satoshi, balance_opt: Option[MilliSatoshi]) {
-
-      def maxHtlcAmount(reservedCapacity: MilliSatoshi): MilliSatoshi = Seq(
-        balance_opt.map(balance => balance - reservedCapacity),
-        params.htlcMaximum_opt,
-        Some(capacity.toMilliSatoshi - reservedCapacity)
-      ).flatten.min.max(0 msat)
-
       def fee(amount: MilliSatoshi): MilliSatoshi = params.fee(amount)
     }
 
diff --git a/eclair-core/src/main/scala/fr/acinq/eclair/router/RouteCalculation.scala b/eclair-core/src/main/scala/fr/acinq/eclair/router/RouteCalculation.scala
index dd03794..cba5f42 100644
--- a/eclair-core/src/main/scala/fr/acinq/eclair/router/RouteCalculation.scala
+++ b/eclair-core/src/main/scala/fr/acinq/eclair/router/RouteCalculation.scala
@@ -390,14 +390,7 @@ object RouteCalculation {
                          pendingHtlcs: Seq[Route] = Nil,
                          routeParams: RouteParams,
                          currentBlockHeight: BlockHeight): Try[Seq[Route]] = Try {
-    val result = findMultiPartRouteInternal(g, localNodeId, targetNodeId, amount, maxFee, extraEdges, ignoredEdges, ignoredVertices, pendingHtlcs, routeParams, currentBlockHeight) match {
-      case Right(routes) => Right(routes)
-      case Left(RouteNotFound) if routeParams.randomize =>
-        // If we couldn't find a randomized solution, fallback to a deterministic one.
-        findMultiPartRouteInternal(g, localNodeId, targetNodeId, amount, maxFee, extraEdges, ignoredEdges, ignoredVertices, pendingHtlcs, routeParams.copy(randomize = false), currentBlockHeight)
-      case Left(ex) => Left(ex)
-    }
-    result match {
+    findMultiPartRouteInternal(g, localNodeId, targetNodeId, amount, maxFee, extraEdges, ignoredEdges, ignoredVertices, pendingHtlcs, routeParams, currentBlockHeight) match {
       case Right(routes) => routes
       case Left(ex) => return Failure(ex)
     }
@@ -413,7 +406,8 @@ object RouteCalculation {
                                          ignoredVertices: Set[PublicKey] = Set.empty,
                                          pendingHtlcs: Seq[Route] = Nil,
                                          routeParams: RouteParams,
-                                         currentBlockHeight: BlockHeight): Either[RouterException, Seq[Route]] = {
+                                         currentBlockHeight: BlockHeight,
+                                         now: TimestampSecond = TimestampSecond.now()): Either[RouterException, Seq[Route]] = {
     // We use Yen's k-shortest paths to find many paths for chunks of the total amount.
     // When the recipient is a direct peer, we have complete visibility on our local channels so we can use more accurate MPP parameters.
     val routeParams1 = {
@@ -429,63 +423,124 @@ object RouteCalculation {
       // We want to ensure that the set of routes we find have enough capacity to allow sending the total amount,
       // without excluding routes with small capacity when the total amount is small.
       val minPartAmount = routeParams.mpp.minPartAmount.max(amount / numRoutes).min(amount)
-      routeParams.copy(mpp = MultiPartParams(minPartAmount, numRoutes))
+      routeParams.copy(mpp = MultiPartParams(minPartAmount, numRoutes, routeParams.mpp.splittingStrategy))
     }
     findRouteInternal(g, localNodeId, targetNodeId, routeParams1.mpp.minPartAmount, maxFee, routeParams1.mpp.maxParts, extraEdges, ignoredEdges, ignoredVertices, routeParams1, currentBlockHeight) match {
-      case Right(routes) =>
+      case Right(paths) =>
         // We use these shortest paths to find a set of non-conflicting HTLCs that send the total amount.
-        split(amount, mutable.Queue(routes: _*), initializeUsedCapacity(pendingHtlcs), routeParams1) match {
+        split(amount, mutable.Queue(paths: _*), initializeUsedCapacity(pendingHtlcs), routeParams1, g.balances, now) match {
           case Right(routes) if validateMultiPartRoute(amount, maxFee, routes, routeParams.includeLocalChannelCost) => Right(routes)
+          case Right(_) if routeParams.randomize =>
+            // We've found a multipart route, but it's too expensive. We try again without randomization to prioritize cheaper paths.
+            val sortedPaths = paths.sortBy(_.weight.weight)
+            split(amount, mutable.Queue(sortedPaths: _*), initializeUsedCapacity(pendingHtlcs), routeParams1, g.balances, now) match {
+              case Right(routes) if validateMultiPartRoute(amount, maxFee, routes, routeParams.includeLocalChannelCost) => Right(routes)
+              case _ => Left(RouteNotFound)
+            }
           case _ => Left(RouteNotFound)
         }
       case Left(ex) => Left(ex)
     }
   }
 
-  @tailrec
-  private def split(amount: MilliSatoshi, paths: mutable.Queue[WeightedPath[PaymentPathWeight]], usedCapacity: mutable.Map[ShortChannelId, MilliSatoshi], routeParams: RouteParams, selectedRoutes: Seq[Route] = Nil): Either[RouterException, Seq[Route]] = {
-    if (amount == 0.msat) {
-      Right(selectedRoutes)
-    } else if (paths.isEmpty) {
-      Left(RouteNotFound)
-    } else {
+  private case class CandidateRoute(route: Route, maxAmount: MilliSatoshi)
+
+  private def split(amount: MilliSatoshi, paths: mutable.Queue[WeightedPath[PaymentPathWeight]], usedCapacity: mutable.Map[ShortChannelId, MilliSatoshi], routeParams: RouteParams, balances: BalancesEstimates, now: TimestampSecond): Either[RouterException, Seq[Route]] = {
+    var amountLeft = amount
+    var candidates: List[CandidateRoute] = Nil
+    // We build some candidate route but may adjust the amounts later if the don't cover the full amount we need to send.
+    while(paths.nonEmpty && amountLeft > 0.msat) {
       val current = paths.dequeue()
       val candidate = computeRouteMaxAmount(current.path, usedCapacity)
-      if (candidate.amount < routeParams.mpp.minPartAmount.min(amount)) {
-        // this route doesn't have enough capacity left: we remove it and continue.
-        split(amount, paths, usedCapacity, routeParams, selectedRoutes)
-      } else {
-        val route = if (routeParams.randomize) {
-          // randomly choose the amount to be between 20% and 100% of the available capacity.
-          val randomizedAmount = candidate.amount * ((20d + Random.nextInt(81)) / 100)
-          if (randomizedAmount < routeParams.mpp.minPartAmount) {
-            candidate.copy(amount = routeParams.mpp.minPartAmount.min(amount))
-          } else {
-            candidate.copy(amount = randomizedAmount.min(amount))
-          }
+      if (candidate.amount >= routeParams.mpp.minPartAmount.min(amountLeft)) {
+        val chosenAmount = routeParams.mpp.splittingStrategy match {
+          case MultiPartParams.Randomize =>
+            // randomly choose the amount to be between 20% and 100% of the available capacity.
+            val randomizedAmount = candidate.amount * ((20d + Random.nextInt(81)) / 100)
+            randomizedAmount.max(routeParams.mpp.minPartAmount).min(amountLeft)
+          case MultiPartParams.MaxExpectedAmount =>
+            val bestAmount = optimizeExpectedValue(current.path, candidate.amount, usedCapacity, routeParams.heuristics.usePastRelaysData, balances, now)
+            bestAmount.max(routeParams.mpp.minPartAmount).min(amountLeft)
+          case MultiPartParams.FullCapacity =>
+            candidate.amount.min(amountLeft)
+        }
+        // We update the route with our chosen amount, which is always smaller than the maximum amount.
+        val chosenRoute = CandidateRoute(candidate.copy(amount = chosenAmount), candidate.amount)
+        // But we use the route with its maximum amount when updating the used capacity, because we may use more funds below when adjusting the amounts.
+        updateUsedCapacity(candidate, usedCapacity)
+        candidates = chosenRoute :: candidates
+        amountLeft = amountLeft - chosenAmount
+        paths.enqueue(current)
+      }
+    }
+    // We adjust the amounts to send through each route.
+    val totalMaximum = candidates.map(_.maxAmount).sum
+    if (amountLeft == 0.msat) {
+      Right(candidates.map(_.route))
+    } else if (totalMaximum < amount) {
+      Left(RouteNotFound)
+    } else {
+      val totalChosen = candidates.map(_.route.amount).sum
+      val additionalFraction = (amount - totalChosen).toLong.toDouble / (totalMaximum - totalChosen).toLong.toDouble
+      var routes: List[Route] = Nil
+      var amountLeft = amount
+      candidates.foreach { case CandidateRoute(route, maxAmount) =>
+        if (amountLeft > 0.msat) {
+          val additionalAmount = MilliSatoshi(((maxAmount - route.amount).toLong * additionalFraction).ceil.toLong)
+          val amountToSend = (route.amount + additionalAmount).min(amountLeft)
+          routes = route.copy(amount = amountToSend) :: routes
+          amountLeft = amountLeft - amountToSend
+        }
+      }
+      Right(routes)
+    }
+  }
+
+  private def optimizeExpectedValue(route: Seq[GraphEdge], capacity: MilliSatoshi, usedCapacity: mutable.Map[ShortChannelId, MilliSatoshi], usePastRelaysData: Boolean, balances: BalancesEstimates, now: TimestampSecond): MilliSatoshi = {
+    // We search the maximum value of a polynomial between its two smallest roots (0 and the minimum channel capacity on the path).
+    // We use binary search to find where the derivative changes sign.
+    var low = 1L
+    var high = capacity.toLong
+    while (high - low > 1L) {
+      val x = (high + low) / 2
+      val d = route.drop(1).foldLeft(1.0 / x.toDouble) { case (total, edge) =>
+        // We compute the success probability `p` for this edge, and its derivative `dp`.
+        val (p, dp) = if (usePastRelaysData) {
+          balances.get(edge).canSendAndDerivative(MilliSatoshi(x), now)
         } else {
-          candidate.copy(amount = candidate.amount.min(amount))
+          // If not using past relays data, we assume that balances are uniformly distributed between 0 and the full capacity of the channel.
+          val c = (edge.capacity - usedCapacity.getOrElse(edge.desc.shortChannelId, 0 msat)).toLong.toDouble
+          (1.0 - x.toDouble / c, -1.0 / c)
         }
-        updateUsedCapacity(route, usedCapacity)
-        // NB: we re-enqueue the current path, it may still have capacity for a second HTLC.
-        split(amount - route.amount, paths.enqueue(current), usedCapacity, routeParams, route +: selectedRoutes)
+        total + dp / p
+      }
+      if (d > 0.0) {
+        low = x
+      } else {
+        high = x
       }
     }
+    MilliSatoshi(high)
   }
 
   /** Compute the maximum amount that we can send through the given route. */
   private def computeRouteMaxAmount(route: Seq[GraphEdge], usedCapacity: mutable.Map[ShortChannelId, MilliSatoshi]): Route = {
-    val firstHopMaxAmount = route.head.maxHtlcAmount(usedCapacity.getOrElse(route.head.desc.shortChannelId, 0 msat))
+    val firstHopMaxAmount = maxEdgeAmount(route.head, usedCapacity.getOrElse(route.head.desc.shortChannelId, 0 msat))
     val amount = route.drop(1).foldLeft(firstHopMaxAmount) { case (amount, edge) =>
       // We compute fees going forward instead of backwards. That means we will slightly overestimate the fees of some
       // edges, but we will always stay inside the capacity bounds we computed.
       val amountMinusFees = amount - edge.fee(amount)
-      val edgeMaxAmount = edge.maxHtlcAmount(usedCapacity.getOrElse(edge.desc.shortChannelId, 0 msat))
+      val edgeMaxAmount = maxEdgeAmount(edge, usedCapacity.getOrElse(edge.desc.shortChannelId, 0 msat))
       amountMinusFees.min(edgeMaxAmount)
     }
     Route(amount.max(0 msat), route.map(graphEdgeToHop), None)
   }
 
+  private def maxEdgeAmount(edge: GraphEdge, usedCapacity: MilliSatoshi): MilliSatoshi = {
+    val maxBalance = edge.balance_opt.getOrElse(edge.params.htlcMaximum_opt.getOrElse(edge.capacity.toMilliSatoshi))
+    Seq(Some(maxBalance - usedCapacity), edge.params.htlcMaximum_opt).flatten.min.max(0 msat)
+  }
+
   /** Initialize known used capacity based on pending HTLCs. */
   private def initializeUsedCapacity(pendingHtlcs: Seq[Route]): mutable.Map[ShortChannelId, MilliSatoshi] = {
     val usedCapacity = mutable.Map.empty[ShortChannelId, MilliSatoshi]
@@ -497,7 +552,14 @@ object RouteCalculation {
 
   /** Update used capacity by taking into account an HTLC sent to the given route. */
   private def updateUsedCapacity(route: Route, usedCapacity: mutable.Map[ShortChannelId, MilliSatoshi]): Unit = {
-    route.hops.foldRight(route.amount) { case (hop, amount) =>
+    val finalHopAmount = route.finalHop_opt.map(hop => {
+      hop match {
+        case BlindedHop(dummyId, _) => usedCapacity.updateWith(dummyId)(previous => Some(route.amount + previous.getOrElse(0 msat)))
+        case _: NodeHop => ()
+      }
+      route.amount + hop.fee(route.amount)
+    }).getOrElse(route.amount)
+    route.hops.foldRight(finalHopAmount) { case (hop, amount) =>
       usedCapacity.updateWith(hop.shortChannelId)(previous => Some(amount + previous.getOrElse(0 msat)))
       amount + hop.fee(amount)
     }
diff --git a/eclair-core/src/main/scala/fr/acinq/eclair/router/Router.scala b/eclair-core/src/main/scala/fr/acinq/eclair/router/Router.scala
index 479dd5a..28b8e95 100644
--- a/eclair-core/src/main/scala/fr/acinq/eclair/router/Router.scala
+++ b/eclair-core/src/main/scala/fr/acinq/eclair/router/Router.scala
@@ -38,7 +38,7 @@ import fr.acinq.eclair.payment.send.Recipient
 import fr.acinq.eclair.payment.{Bolt11Invoice, Invoice}
 import fr.acinq.eclair.remote.EclairInternalsSerializer.RemoteTypes
 import fr.acinq.eclair.router.Graph.GraphStructure.DirectedGraph
-import fr.acinq.eclair.router.Graph.MessageWeightRatios
+import fr.acinq.eclair.router.Graph.{HeuristicsConstants, MessageWeightRatios}
 import fr.acinq.eclair.router.Monitoring.Metrics
 import fr.acinq.eclair.wire.protocol._
 
@@ -354,7 +354,7 @@ object Router {
 
   case class PathFindingConf(randomize: Boolean,
                              boundaries: SearchBoundaries,
-                             heuristics: Graph.WeightRatios[Graph.PaymentPathWeight],
+                             heuristics: HeuristicsConstants,
                              mpp: MultiPartParams,
                              experimentName: String,
                              experimentPercentage: Int) {
@@ -577,11 +577,24 @@ object Router {
     override def fee(amount: MilliSatoshi): MilliSatoshi = fee
   }
 
-  case class MultiPartParams(minPartAmount: MilliSatoshi, maxParts: Int)
+  object MultiPartParams {
+    sealed trait SplittingStrategy
+
+    /** Send the full capacity of the route */
+    object FullCapacity extends SplittingStrategy
+
+    /** Send between 20% and 100% of the capacity of the route */
+    object Randomize extends SplittingStrategy
+
+    /** Maximize the expected delivered amount */
+    object MaxExpectedAmount extends SplittingStrategy
+  }
+
+  case class MultiPartParams(minPartAmount: MilliSatoshi, maxParts: Int, splittingStrategy: MultiPartParams.SplittingStrategy)
 
   case class RouteParams(randomize: Boolean,
                          boundaries: SearchBoundaries,
-                         heuristics: Graph.WeightRatios[Graph.PaymentPathWeight],
+                         heuristics: HeuristicsConstants,
                          mpp: MultiPartParams,
                          experimentName: String,
                          includeLocalChannelCost: Boolean) {
diff --git a/eclair-core/src/test/scala/fr/acinq/eclair/EclairImplSpec.scala b/eclair-core/src/test/scala/fr/acinq/eclair/EclairImplSpec.scala
index 0febbc5..6623043 100644
--- a/eclair-core/src/test/scala/fr/acinq/eclair/EclairImplSpec.scala
+++ b/eclair-core/src/test/scala/fr/acinq/eclair/EclairImplSpec.scala
@@ -231,11 +231,11 @@ class EclairImplSpec extends TestKitBaseClass with FixtureAnyFunSuiteLike with I
     assert(Announcements.isNode1(b, c))
 
     val channels = SortedMap(Seq(
-      (ann_ab, makeUpdateShort(ShortChannelId(1L), a, b, feeBase = 0 msat, 0, minHtlc = 0 msat, maxHtlc = None, cltvDelta = CltvExpiryDelta(13))),
-      (ann_ae, makeUpdateShort(ShortChannelId(4L), a, e, feeBase = 0 msat, 0, minHtlc = 0 msat, maxHtlc = None, cltvDelta = CltvExpiryDelta(12))),
-      (ann_bc, makeUpdateShort(ShortChannelId(2L), b, c, feeBase = 1 msat, 0, minHtlc = 0 msat, maxHtlc = None, cltvDelta = CltvExpiryDelta(500))),
-      (ann_cd, makeUpdateShort(ShortChannelId(3L), c, d, feeBase = 1 msat, 0, minHtlc = 0 msat, maxHtlc = None, cltvDelta = CltvExpiryDelta(500))),
-      (ann_ec, makeUpdateShort(ShortChannelId(7L), e, c, feeBase = 2 msat, 0, minHtlc = 0 msat, maxHtlc = None, cltvDelta = CltvExpiryDelta(12)))
+      (ann_ab, makeUpdateShort(ShortChannelId(1L), a, b, feeBase = 0 msat, 0, minHtlc = 0 msat, maxHtlc = 100000 msat, cltvDelta = CltvExpiryDelta(13))),
+      (ann_ae, makeUpdateShort(ShortChannelId(4L), a, e, feeBase = 0 msat, 0, minHtlc = 0 msat, maxHtlc = 100000 msat, cltvDelta = CltvExpiryDelta(12))),
+      (ann_bc, makeUpdateShort(ShortChannelId(2L), b, c, feeBase = 1 msat, 0, minHtlc = 0 msat, maxHtlc = 100000 msat, cltvDelta = CltvExpiryDelta(500))),
+      (ann_cd, makeUpdateShort(ShortChannelId(3L), c, d, feeBase = 1 msat, 0, minHtlc = 0 msat, maxHtlc = 100000 msat, cltvDelta = CltvExpiryDelta(500))),
+      (ann_ec, makeUpdateShort(ShortChannelId(7L), e, c, feeBase = 2 msat, 0, minHtlc = 0 msat, maxHtlc = 100000 msat, cltvDelta = CltvExpiryDelta(12)))
     ).map { case (ann, update) =>
       update.shortChannelId -> PublicChannel(ann, TxId(ByteVector32.Zeroes), 100 sat, Some(update.copy(channelFlags = ChannelUpdate.ChannelFlags.DUMMY)), None, None)
     }: _*)
diff --git a/eclair-core/src/test/scala/fr/acinq/eclair/TestConstants.scala b/eclair-core/src/test/scala/fr/acinq/eclair/TestConstants.scala
index e96cec0..433d97a 100644
--- a/eclair-core/src/test/scala/fr/acinq/eclair/TestConstants.scala
+++ b/eclair-core/src/test/scala/fr/acinq/eclair/TestConstants.scala
@@ -231,6 +231,7 @@ object TestConstants {
           mpp = MultiPartParams(
             minPartAmount = 15000000 msat,
             maxParts = 10,
+            splittingStrategy = MultiPartParams.FullCapacity
           ),
           experimentName = "alice-test-experiment",
           experimentPercentage = 100))),
@@ -422,6 +423,7 @@ object TestConstants {
           mpp = MultiPartParams(
             minPartAmount = 15000000 msat,
             maxParts = 10,
+            splittingStrategy = MultiPartParams.FullCapacity
           ),
           experimentName = "bob-test-experiment",
           experimentPercentage = 100))),
diff --git a/eclair-core/src/test/scala/fr/acinq/eclair/integration/IntegrationSpec.scala b/eclair-core/src/test/scala/fr/acinq/eclair/integration/IntegrationSpec.scala
index a078ec6..be17b97 100644
--- a/eclair-core/src/test/scala/fr/acinq/eclair/integration/IntegrationSpec.scala
+++ b/eclair-core/src/test/scala/fr/acinq/eclair/integration/IntegrationSpec.scala
@@ -64,7 +64,7 @@ abstract class IntegrationSpec extends TestKitBaseClass with BitcoindService wit
       useLogProbability = false,
       usePastRelaysData = false
     ),
-    mpp = MultiPartParams(15000000 msat, 6),
+    mpp = MultiPartParams(15000000 msat, 6, MultiPartParams.FullCapacity),
     experimentName = "my-test-experiment",
     experimentPercentage = 100
   ).getDefaultRouteParams
diff --git a/eclair-core/src/test/scala/fr/acinq/eclair/payment/MultiPartPaymentLifecycleSpec.scala b/eclair-core/src/test/scala/fr/acinq/eclair/payment/MultiPartPaymentLifecycleSpec.scala
index 66d3486..ececd0b 100644
--- a/eclair-core/src/test/scala/fr/acinq/eclair/payment/MultiPartPaymentLifecycleSpec.scala
+++ b/eclair-core/src/test/scala/fr/acinq/eclair/payment/MultiPartPaymentLifecycleSpec.scala
@@ -697,7 +697,7 @@ object MultiPartPaymentLifecycleSpec {
       6,
       CltvExpiryDelta(1008)),
     HeuristicsConstants(0, RelayFees(0 msat, 0), RelayFees(0 msat, 0), useLogProbability = false, usePastRelaysData = false),
-    MultiPartParams(1000 msat, 5),
+    MultiPartParams(1000 msat, 5, MultiPartParams.FullCapacity),
     experimentName = "my-test-experiment",
     experimentPercentage = 100
   ).getDefaultRouteParams
diff --git a/eclair-core/src/test/scala/fr/acinq/eclair/payment/PaymentLifecycleSpec.scala b/eclair-core/src/test/scala/fr/acinq/eclair/payment/PaymentLifecycleSpec.scala
index 58b63fd..101c8bc 100644
--- a/eclair-core/src/test/scala/fr/acinq/eclair/payment/PaymentLifecycleSpec.scala
+++ b/eclair-core/src/test/scala/fr/acinq/eclair/payment/PaymentLifecycleSpec.scala
@@ -302,7 +302,7 @@ class PaymentLifecycleSpec extends BaseRouterSpec {
       randomize = false,
       boundaries = SearchBoundaries(100 msat, 0.0, 20, CltvExpiryDelta(2016)),
       HeuristicsConstants(0, RelayFees(0 msat, 0), RelayFees(0 msat, 0), useLogProbability = false, usePastRelaysData = false),
-      MultiPartParams(10_000 msat, 5),
+      MultiPartParams(10_000 msat, 5, MultiPartParams.FullCapacity),
       "my-test-experiment",
       experimentPercentage = 100
     ).getDefaultRouteParams
diff --git a/eclair-core/src/test/scala/fr/acinq/eclair/router/RouteCalculationSpec.scala b/eclair-core/src/test/scala/fr/acinq/eclair/router/RouteCalculationSpec.scala
index 470a090..7e716db 100644
--- a/eclair-core/src/test/scala/fr/acinq/eclair/router/RouteCalculationSpec.scala
+++ b/eclair-core/src/test/scala/fr/acinq/eclair/router/RouteCalculationSpec.scala
@@ -26,6 +26,7 @@ import fr.acinq.eclair.router.Graph.GraphStructure.DirectedGraph.graphEdgeToHop
 import fr.acinq.eclair.router.Graph.GraphStructure.{DirectedGraph, GraphEdge}
 import fr.acinq.eclair.router.Graph.{HeuristicsConstants, PaymentPathWeight}
 import fr.acinq.eclair.router.RouteCalculation._
+import fr.acinq.eclair.router.Router.MultiPartParams.{FullCapacity, MaxExpectedAmount, Randomize}
 import fr.acinq.eclair.router.Router._
 import fr.acinq.eclair.transactions.Transactions
 import fr.acinq.eclair.wire.protocol._
@@ -766,6 +767,7 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
       .modify(_.boundaries.maxFeeFlat).setTo(7 msat)
       .modify(_.boundaries.maxFeeProportional).setTo(0)
       .modify(_.randomize).setTo(true)
+      .modify(_.mpp.splittingStrategy).setTo(Randomize)
     val strictFee = strictFeeParams.getMaxFee(DEFAULT_AMOUNT_MSAT)
     assert(strictFee == 7.msat)
 
@@ -905,7 +907,7 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
       makeEdge(4L, a, b, 100 msat, 20, minHtlc = 1 msat, balance_opt = Some(16000 msat)),
     )), 1 day)
     // We set max-parts to 3, but it should be ignored when sending to a direct neighbor.
-    val routeParams = DEFAULT_ROUTE_PARAMS.copy(mpp = MultiPartParams(2500 msat, 3))
+    val routeParams = DEFAULT_ROUTE_PARAMS.copy(mpp = MultiPartParams(2500 msat, 3, DEFAULT_ROUTE_PARAMS.mpp.splittingStrategy))
 
     {
       val Success(routes) = findMultiPartRoute(g, a, b, amount, 1 msat, routeParams = routeParams, currentBlockHeight = BlockHeight(400000))
@@ -914,14 +916,20 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
       checkRouteAmounts(routes, amount, 0 msat)
     }
     {
-      val Success(routes) = findMultiPartRoute(g, a, b, amount, 1 msat, routeParams = routeParams.copy(randomize = true), currentBlockHeight = BlockHeight(400000))
+      val Success(routes) = findMultiPartRoute(g, a, b, amount, 1 msat, routeParams = routeParams.copy(randomize = true).modify(_.mpp.splittingStrategy).setTo(Randomize), currentBlockHeight = BlockHeight(400000))
+      assert(routes.length >= 4, routes)
+      assert(routes.forall(_.hops.length == 1), routes)
+      checkRouteAmounts(routes, amount, 0 msat)
+    }
+    {
+      val Success(routes) = findMultiPartRoute(g, a, b, amount, 1 msat, routeParams = routeParams.modify(_.mpp.splittingStrategy).setTo(MaxExpectedAmount), currentBlockHeight = BlockHeight(400000))
       assert(routes.length >= 4, routes)
       assert(routes.forall(_.hops.length == 1), routes)
       checkRouteAmounts(routes, amount, 0 msat)
     }
     {
       // We set min-part-amount to a value that excludes channels 1 and 4.
-      val failure = findMultiPartRoute(g, a, b, amount, 1 msat, routeParams = routeParams.copy(mpp = MultiPartParams(16500 msat, 3)), currentBlockHeight = BlockHeight(400000))
+      val failure = findMultiPartRoute(g, a, b, amount, 1 msat, routeParams = routeParams.copy(mpp = MultiPartParams(16500 msat, 3, routeParams.mpp.splittingStrategy)), currentBlockHeight = BlockHeight(400000))
       assert(failure == Failure(RouteNotFound))
     }
   }
@@ -977,7 +985,14 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
       checkRouteAmounts(routes, amount, 0 msat)
     }
     {
-      val Success(routes) = findMultiPartRoute(g, a, b, amount, 1 msat, routeParams = DEFAULT_ROUTE_PARAMS.copy(randomize = true), currentBlockHeight = BlockHeight(400000))
+      val Success(routes) = findMultiPartRoute(g, a, b, amount, 1 msat, routeParams = DEFAULT_ROUTE_PARAMS.copy(randomize = true).modify(_.mpp.splittingStrategy).setTo(Randomize), currentBlockHeight = BlockHeight(400000))
+      assert(routes.length >= 3, routes)
+      assert(routes.forall(_.hops.length == 1), routes)
+      checkIgnoredChannels(routes, 2L)
+      checkRouteAmounts(routes, amount, 0 msat)
+    }
+    {
+      val Success(routes) = findMultiPartRoute(g, a, b, amount, 1 msat, routeParams = DEFAULT_ROUTE_PARAMS.modify(_.mpp.splittingStrategy).setTo(MaxExpectedAmount), currentBlockHeight = BlockHeight(400000))
       assert(routes.length >= 3, routes)
       assert(routes.forall(_.hops.length == 1), routes)
       checkIgnoredChannels(routes, 2L)
@@ -1048,7 +1063,7 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
     )), 1 day)
 
     val amount = 30000 msat
-    val routeParams = DEFAULT_ROUTE_PARAMS.copy(mpp = MultiPartParams(2500 msat, 5))
+    val routeParams = DEFAULT_ROUTE_PARAMS.copy(mpp = MultiPartParams(2500 msat, 5, DEFAULT_ROUTE_PARAMS.mpp.splittingStrategy))
     val Success(routes) = findMultiPartRoute(g, a, b, amount, 1 msat, routeParams = routeParams, currentBlockHeight = BlockHeight(400000))
     assert(routes.forall(_.hops.length == 1), routes)
     assert(routes.length == 3, routes)
@@ -1087,7 +1102,11 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
       assert(result == Failure(RouteNotFound))
     }
     {
-      val result = findMultiPartRoute(g, a, b, 40000 msat, 1 msat, routeParams = DEFAULT_ROUTE_PARAMS.copy(randomize = true), currentBlockHeight = BlockHeight(400000))
+      val result = findMultiPartRoute(g, a, b, 40000 msat, 1 msat, routeParams = DEFAULT_ROUTE_PARAMS.copy(randomize = true).modify(_.mpp.splittingStrategy).setTo(Randomize), currentBlockHeight = BlockHeight(400000))
+      assert(result == Failure(RouteNotFound))
+    }
+    {
+      val result = findMultiPartRoute(g, a, b, 40000 msat, 1 msat, routeParams = DEFAULT_ROUTE_PARAMS.modify(_.mpp.splittingStrategy).setTo(MaxExpectedAmount), currentBlockHeight = BlockHeight(400000))
       assert(result == Failure(RouteNotFound))
     }
   }
@@ -1116,7 +1135,11 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
       assert(result == Failure(RouteNotFound))
     }
     {
-      val result = findMultiPartRoute(g, a, b, 10000 msat, 1 msat, routeParams = DEFAULT_ROUTE_PARAMS.copy(randomize = true), currentBlockHeight = BlockHeight(400000))
+      val result = findMultiPartRoute(g, a, b, 10000 msat, 1 msat, routeParams = DEFAULT_ROUTE_PARAMS.copy(randomize = true).modify(_.mpp.splittingStrategy).setTo(Randomize), currentBlockHeight = BlockHeight(400000))
+      assert(result == Failure(RouteNotFound))
+    }
+    {
+      val result = findMultiPartRoute(g, a, b, 10000 msat, 1 msat, routeParams = DEFAULT_ROUTE_PARAMS.modify(_.mpp.splittingStrategy).setTo(MaxExpectedAmount), currentBlockHeight = BlockHeight(400000))
       assert(result == Failure(RouteNotFound))
     }
   }
@@ -1145,14 +1168,18 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
     }
     {
       // Update A - B with unknown balance, capacity should be used instead.
-      val g1 = g.addEdge(edge_ab.copy(capacity = 15 sat, balance_opt = None))
+      val g1 = g.addEdge(makeEdge(1L, a, b, 50 msat, 100, minHtlc = 1 msat, capacity = 15 sat, balance_opt = None))
       val Success(routes) = findMultiPartRoute(g1, a, e, amount, maxFee, routeParams = DEFAULT_ROUTE_PARAMS, currentBlockHeight = BlockHeight(400000))
       checkRouteAmounts(routes, amount, maxFee)
       assert(routes2Ids(routes) == Set(Seq(1L, 2L, 3L), Seq(4L, 6L), Seq(5L, 6L)))
     }
     {
       // Randomize routes.
-      val Success(routes) = findMultiPartRoute(g, a, e, amount, maxFee, routeParams = DEFAULT_ROUTE_PARAMS.copy(randomize = true), currentBlockHeight = BlockHeight(400000))
+      val Success(routes) = findMultiPartRoute(g, a, e, amount, maxFee, routeParams = DEFAULT_ROUTE_PARAMS.copy(randomize = true).modify(_.mpp.splittingStrategy).setTo(Randomize), currentBlockHeight = BlockHeight(400000))
+      checkRouteAmounts(routes, amount, maxFee)
+    }
+    {
+      val Success(routes) = findMultiPartRoute(g, a, e, amount, maxFee, routeParams = DEFAULT_ROUTE_PARAMS.modify(_.mpp.splittingStrategy).setTo(MaxExpectedAmount), currentBlockHeight = BlockHeight(400000))
       checkRouteAmounts(routes, amount, maxFee)
     }
     {
@@ -1163,7 +1190,7 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
     }
     {
       // Update capacity A - B to be too low.
-      val g1 = g.addEdge(edge_ab.copy(capacity = 5 sat, balance_opt = None))
+      val g1 = g.addEdge(makeEdge(1L, a, b, 50 msat, 100, minHtlc = 1 msat, capacity = 5 sat, balance_opt = None))
       val failure = findMultiPartRoute(g1, a, e, amount, maxFee, routeParams = DEFAULT_ROUTE_PARAMS, currentBlockHeight = BlockHeight(400000))
       assert(failure == Failure(RouteNotFound))
     }
@@ -1180,7 +1207,7 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
     // |               |
     // +--- B --- D ---+
     // Our balance and the amount we want to send are below the minimum part amount.
-    val routeParams = DEFAULT_ROUTE_PARAMS.copy(mpp = MultiPartParams(5000 msat, 5))
+    val routeParams = DEFAULT_ROUTE_PARAMS.copy(mpp = MultiPartParams(5000 msat, 5, DEFAULT_ROUTE_PARAMS.mpp.splittingStrategy))
     val g = GraphWithBalanceEstimates(DirectedGraph(List(
       makeEdge(1L, a, b, 50 msat, 100, minHtlc = 1 msat, balance_opt = Some(1500 msat)),
       makeEdge(2L, b, d, 15 msat, 0, minHtlc = 1 msat, capacity = 25 sat),
@@ -1242,12 +1269,16 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
     }
     {
       // Randomize routes.
-      val Success(routes) = findMultiPartRoute(g, a, f, amount, maxFee, routeParams = DEFAULT_ROUTE_PARAMS.copy(randomize = true), currentBlockHeight = BlockHeight(400000))
+      val Success(routes) = findMultiPartRoute(g, a, f, amount, maxFee, routeParams = DEFAULT_ROUTE_PARAMS.copy(randomize = true).modify(_.mpp.splittingStrategy).setTo(Randomize), currentBlockHeight = BlockHeight(400000))
+      checkRouteAmounts(routes, amount, maxFee)
+    }
+    {
+      val Success(routes) = findMultiPartRoute(g, a, f, amount, maxFee, routeParams = DEFAULT_ROUTE_PARAMS.modify(_.mpp.splittingStrategy).setTo(MaxExpectedAmount), currentBlockHeight = BlockHeight(400000))
       checkRouteAmounts(routes, amount, maxFee)
     }
     {
       // Update A - B with unknown balance, capacity should be used instead.
-      val g1 = g.addEdge(edge_ab.copy(capacity = 500 sat, balance_opt = None))
+      val g1 = g.addEdge(makeEdge(1L, a, b, 50 msat, 100, minHtlc = 1 msat, capacity = 500 sat, balance_opt = None))
       val Success(routes) = findMultiPartRoute(g1, a, f, amount, maxFee, routeParams = DEFAULT_ROUTE_PARAMS, currentBlockHeight = BlockHeight(400000))
       checkRouteAmounts(routes, amount, maxFee)
       assert(routes2Ids(routes) == Set(Seq(1L, 2L, 3L, 5L), Seq(1L, 4L, 5L), Seq(1L, 6L, 7L)))
@@ -1260,7 +1291,7 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
     }
     {
       // Update capacity A - B to be too low to cover fees.
-      val g1 = g.addEdge(edge_ab.copy(capacity = 400 sat, balance_opt = None))
+      val g1 = g.addEdge(makeEdge(1L, a, b, 50 msat, 100, minHtlc = 1 msat, capacity = 400 sat, balance_opt = None))
       val failure = findMultiPartRoute(g1, a, f, amount, maxFee, routeParams = DEFAULT_ROUTE_PARAMS, currentBlockHeight = BlockHeight(400000))
       assert(failure == Failure(RouteNotFound))
     }
@@ -1300,7 +1331,7 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
     {
       val amount = 15_000_000 msat
       val maxFee = 50_000 msat // this fee is enough to go through the preferred route
-      val routeParams = DEFAULT_ROUTE_PARAMS.copy(randomize = false, mpp = MultiPartParams(50_000 msat, 5))
+      val routeParams = DEFAULT_ROUTE_PARAMS.copy(randomize = false, mpp = MultiPartParams(50_000 msat, 5, FullCapacity))
       val Success(routes) = findMultiPartRoute(g, a, d, amount, maxFee, routeParams = routeParams, currentBlockHeight = BlockHeight(400000))
       checkRouteAmounts(routes, amount, maxFee)
       assert(routes2Ids(routes) == Set(Seq(100L, 101L)))
@@ -1308,14 +1339,14 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
     {
       val amount = 15_000_000 msat
       val maxFee = 10_000 msat // this fee is too low to go through the preferred route
-      val routeParams = DEFAULT_ROUTE_PARAMS.copy(randomize = false, mpp = MultiPartParams(50_000 msat, 5))
+      val routeParams = DEFAULT_ROUTE_PARAMS.copy(randomize = false, mpp = MultiPartParams(50_000 msat, 5, FullCapacity))
       val failure = findMultiPartRoute(g, a, d, amount, maxFee, routeParams = routeParams, currentBlockHeight = BlockHeight(400000))
       assert(failure == Failure(RouteNotFound))
     }
     {
       val amount = 5_000_000 msat
       val maxFee = 10_000 msat // this fee is enough to go through the preferred route, but the cheaper ones can handle it
-      val routeParams = DEFAULT_ROUTE_PARAMS.copy(randomize = false, mpp = MultiPartParams(50_000 msat, 5))
+      val routeParams = DEFAULT_ROUTE_PARAMS.copy(randomize = false, mpp = MultiPartParams(50_000 msat, 5, FullCapacity))
       val Success(routes) = findMultiPartRoute(g, a, d, amount, maxFee, routeParams = routeParams, currentBlockHeight = BlockHeight(400000))
       assert(routes.length == 5)
       routes.foreach(route => {
@@ -1357,35 +1388,6 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
     assert(routes2Ids(routes) == Set(Seq(8L), Seq(9L, 10L)))
   }
 
-  test("calculate multipart route to remote node (restricted htlc_minimum_msat and htlc_maximum_msat)") {
-    // +----- B -----+
-    // |             |
-    // A----- C ---- E
-    // |             |
-    // +----- D -----+
-    val (amount, maxFee) = (15000 msat, 5 msat)
-    val g = GraphWithBalanceEstimates(DirectedGraph(List(
-      // The A -> B -> E path is impossible because the A -> B balance is lower than the B -> E htlc_minimum_msat.
-      makeEdge(1L, a, b, 1 msat, 0, minHtlc = 500 msat, balance_opt = Some(7000 msat)),
-      makeEdge(2L, b, e, 1 msat, 0, minHtlc = 10000 msat, capacity = 50 sat),
-      makeEdge(3L, a, c, 1 msat, 0, minHtlc = 500 msat, balance_opt = Some(10000 msat)),
-      makeEdge(4L, c, e, 1 msat, 0, minHtlc = 500 msat, maxHtlc = Some(4000 msat), capacity = 50 sat),
-      makeEdge(5L, a, d, 1 msat, 0, minHtlc = 500 msat, balance_opt = Some(10000 msat)),
-      makeEdge(6L, d, e, 1 msat, 0, minHtlc = 500 msat, maxHtlc = Some(4000 msat), capacity = 50 sat),
-    )), 1 day)
-
-    val Success(routes) = findMultiPartRoute(g, a, e, amount, maxFee, routeParams = DEFAULT_ROUTE_PARAMS, currentBlockHeight = BlockHeight(400000))
-    checkRouteAmounts(routes, amount, maxFee)
-    assert(routes.length >= 4, routes)
-    assert(routes.forall(_.amount <= 4000.msat), routes)
-    assert(routes.forall(_.amount >= 500.msat), routes)
-    checkIgnoredChannels(routes, 1L, 2L)
-
-    val maxFeeTooLow = 3 msat
-    val failure = findMultiPartRoute(g, a, e, amount, maxFeeTooLow, routeParams = DEFAULT_ROUTE_PARAMS, currentBlockHeight = BlockHeight(400000))
-    assert(failure == Failure(RouteNotFound))
-  }
-
   test("calculate multipart route to remote node (complex graph)") {
     // +---+                       +---+    +---+
     // | A |-----+            +--->| B |--->| C |
@@ -1405,7 +1407,7 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
       makeEdge(6L, b, c, 5 msat, 50, minHtlc = 1000 msat, capacity = 20 sat),
       makeEdge(7L, c, f, 5 msat, 10, minHtlc = 1500 msat, capacity = 50 sat)
     )), 1 day)
-    val routeParams = DEFAULT_ROUTE_PARAMS.copy(mpp = MultiPartParams(1500 msat, 10))
+    val routeParams = DEFAULT_ROUTE_PARAMS.copy(mpp = MultiPartParams(1500 msat, 10, DEFAULT_ROUTE_PARAMS.mpp.splittingStrategy))
 
     {
       val (amount, maxFee) = (15000 msat, 50 msat)
@@ -1429,7 +1431,12 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
     }
     {
       val (amount, maxFee) = (40000 msat, 100 msat)
-      val Success(routes) = findMultiPartRoute(g, d, f, amount, maxFee, routeParams = routeParams.copy(randomize = true), currentBlockHeight = BlockHeight(400000))
+      val Success(routes) = findMultiPartRoute(g, d, f, amount, maxFee, routeParams = routeParams.copy(randomize = true).modify(_.mpp.splittingStrategy).setTo(Randomize), currentBlockHeight = BlockHeight(400000))
+      checkRouteAmounts(routes, amount, maxFee)
+    }
+    {
+      val (amount, maxFee) = (40000 msat, 100 msat)
+      val Success(routes) = findMultiPartRoute(g, d, f, amount, maxFee, routeParams = routeParams.modify(_.mpp.splittingStrategy).setTo(MaxExpectedAmount), currentBlockHeight = BlockHeight(400000))
       checkRouteAmounts(routes, amount, maxFee)
     }
     {
@@ -1528,13 +1535,63 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
         makeEdge(9L, c, f, Random.nextLong(250).msat, Random.nextInt(10000), minHtlc = Random.nextLong(100).msat, maxHtlc = Some((20000 + Random.nextLong(80000)).msat), CltvExpiryDelta(Random.nextInt(288)), capacity = (10 + Random.nextLong(100)).sat)
       )), 1 day)
 
-      findMultiPartRoute(g, d, f, amount, maxFee, routeParams = DEFAULT_ROUTE_PARAMS.copy(randomize = true), currentBlockHeight = BlockHeight(400000)) match {
+      findMultiPartRoute(g, d, f, amount, maxFee, routeParams = DEFAULT_ROUTE_PARAMS.copy(randomize = true).modify(_.mpp.splittingStrategy).setTo(Randomize), currentBlockHeight = BlockHeight(400000)) match {
         case Success(routes) => checkRouteAmounts(routes, amount, maxFee)
         case Failure(ex) => assert(ex == RouteNotFound)
       }
     }
   }
 
+  test("calculate multipart route to remote node using max expected amount splitting strategy") {
+    // A-------------E
+    // |             |
+    // +----- B -----+
+    // |             |
+    // +----- C ---- +
+    // |             |
+    // +----- D -----+
+    val (amount, maxFee) = (60000 msat, 1000 msat)
+    val g = GraphWithBalanceEstimates(DirectedGraph(List(
+      // The A -> B -> E route is the most economic one, but we already have a pending HTLC in it.
+      makeEdge(0L, a, e, 50 msat, 0, minHtlc = 100 msat, balance_opt = Some(10000 msat)),
+      makeEdge(1L, a, b, 50 msat, 0, minHtlc = 100 msat, balance_opt = Some(100000 msat)),
+      makeEdge(2L, b, e, 50 msat, 0, minHtlc = 100 msat, capacity = 50 sat),
+      makeEdge(3L, a, c, 50 msat, 0, minHtlc = 100 msat, balance_opt = Some(100000 msat)),
+      makeEdge(4L, c, e, 50 msat, 0, minHtlc = 100 msat, capacity = 25 sat),
+      makeEdge(5L, a, d, 50 msat, 0, minHtlc = 100 msat, balance_opt = Some(100000 msat)),
+      makeEdge(6L, d, e, 50 msat, 0, minHtlc = 100 msat, capacity = 25 sat),
+    )), 1 day)
+
+    val routeParams = DEFAULT_ROUTE_PARAMS.copy(mpp = DEFAULT_ROUTE_PARAMS.mpp.copy(splittingStrategy = MultiPartParams.MaxExpectedAmount))
+    val Success(routes) = findMultiPartRoute(g, a, e, amount, maxFee, routeParams = routeParams, currentBlockHeight = BlockHeight(400000))
+    checkRouteAmounts(routes, amount, maxFee)
+    assert(routes.map(route => (route.amount, route.hops.head.shortChannelId.toLong)).toSet == Set((10000 msat, 0L), (25000 msat, 1L), (12500 msat, 3L), (12500 msat, 5L)))
+  }
+
+  test("calculate multipart route to remote node using max expected amount splitting strategy, respect minPartAmount") {
+    // +----- B -----+
+    // |             |
+    // A----- C ---- E
+    // |             |
+    // +----- D -----+
+    val (amount, maxFee) = (55000 msat, 1000 msat)
+    val g = GraphWithBalanceEstimates(DirectedGraph(List(
+      // The A -> B -> E route is the most economic one, but we already have a pending HTLC in it.
+      makeEdge(1L, a, b, 50 msat, 0, minHtlc = 100 msat, balance_opt = Some(100000 msat)),
+      makeEdge(2L, b, e, 50 msat, 0, minHtlc = 100 msat, capacity = 50 sat),
+      makeEdge(3L, a, c, 50 msat, 0, minHtlc = 100 msat, balance_opt = Some(100000 msat)),
+      makeEdge(4L, c, e, 50 msat, 0, minHtlc = 100 msat, capacity = 25 sat),
+      makeEdge(5L, a, d, 50 msat, 0, minHtlc = 100 msat, balance_opt = Some(100000 msat)),
+      makeEdge(6L, d, e, 50 msat, 0, minHtlc = 100 msat, capacity = 25 sat),
+    )), 1 day)
+
+    val routeParams = DEFAULT_ROUTE_PARAMS.copy(mpp = DEFAULT_ROUTE_PARAMS.mpp.copy(minPartAmount = 15000 msat, splittingStrategy = MultiPartParams.MaxExpectedAmount))
+    val Success(routes) = findMultiPartRoute(g, a, e, amount, maxFee, routeParams = routeParams, currentBlockHeight = BlockHeight(400000))
+    assert(routes.forall(_.hops.length == 2), routes)
+    checkRouteAmounts(routes, amount, maxFee)
+    assert(routes.map(route => (route.amount, route.hops.head.shortChannelId.toLong)).toSet == Set((25000 msat, 1L), (15000 msat, 3L), (15000 msat, 5L)))
+  }
+
   test("loop trap") {
     //       +-----------------+
     //       |                 |
@@ -1899,7 +1956,7 @@ object RouteCalculationSpec {
     randomize = false,
     boundaries = SearchBoundaries(21000 msat, 0.03, 6, CltvExpiryDelta(2016)),
     NO_WEIGHT_RATIOS,
-    MultiPartParams(1000 msat, 10),
+    MultiPartParams(1000 msat, 10, FullCapacity),
     experimentName = "my-test-experiment",
     experimentPercentage = 100).getDefaultRouteParams
 
@@ -1920,11 +1977,11 @@ object RouteCalculationSpec {
                cltvDelta: CltvExpiryDelta = CltvExpiryDelta(0),
                capacity: Satoshi = DEFAULT_CAPACITY,
                balance_opt: Option[MilliSatoshi] = None): GraphEdge = {
-    val update = makeUpdateShort(ShortChannelId(shortChannelId), nodeId1, nodeId2, feeBase, feeProportionalMillionth, minHtlc, maxHtlc, cltvDelta)
+    val update = makeUpdateShort(ShortChannelId(shortChannelId), nodeId1, nodeId2, feeBase, feeProportionalMillionth, minHtlc, maxHtlc.getOrElse(capacity.toMilliSatoshi), cltvDelta)
     GraphEdge(ChannelDesc(RealShortChannelId(shortChannelId), nodeId1, nodeId2), HopRelayParams.FromAnnouncement(update), capacity, balance_opt)
   }
 
-  def makeUpdateShort(shortChannelId: ShortChannelId, nodeId1: PublicKey, nodeId2: PublicKey, feeBase: MilliSatoshi, feeProportionalMillionth: Int, minHtlc: MilliSatoshi = DEFAULT_AMOUNT_MSAT, maxHtlc: Option[MilliSatoshi] = None, cltvDelta: CltvExpiryDelta = CltvExpiryDelta(0), timestamp: TimestampSecond = 0 unixsec): ChannelUpdate =
+  def makeUpdateShort(shortChannelId: ShortChannelId, nodeId1: PublicKey, nodeId2: PublicKey, feeBase: MilliSatoshi, feeProportionalMillionth: Int, minHtlc: MilliSatoshi = DEFAULT_AMOUNT_MSAT, maxHtlc: MilliSatoshi = 500_000_000 msat, cltvDelta: CltvExpiryDelta = CltvExpiryDelta(0), timestamp: TimestampSecond = 0 unixsec): ChannelUpdate =
     ChannelUpdate(
       signature = DUMMY_SIG,
       chainHash = Block.RegtestGenesisBlock.hash,
@@ -1936,7 +1993,7 @@ object RouteCalculationSpec {
       htlcMinimumMsat = minHtlc,
       feeBaseMsat = feeBase,
       feeProportionalMillionths = feeProportionalMillionth,
-      htlcMaximumMsat = maxHtlc.getOrElse(500_000_000 msat)
+      htlcMaximumMsat = maxHtlc
     )
 
   def hops2Ids(hops: Seq[ChannelHop]): Seq[Long] = hops.map(hop => hop.shortChannelId.toLong)
diff --git a/eclair-core/src/test/scala/fr/acinq/eclair/router/RouterSpec.scala b/eclair-core/src/test/scala/fr/acinq/eclair/router/RouterSpec.scala
index cd8b6e8..d4d2780 100644
--- a/eclair-core/src/test/scala/fr/acinq/eclair/router/RouterSpec.scala
+++ b/eclair-core/src/test/scala/fr/acinq/eclair/router/RouterSpec.scala
@@ -558,7 +558,7 @@ class RouterSpec extends BaseRouterSpec {
       router ! RouteRequest(sender.ref, a, recipient, DEFAULT_ROUTE_PARAMS, allowMultiPart = true)
       val routes = sender.expectMessageType[RouteResponse].routes
       assert(routes.length == 2)
-      assert(routes.flatMap(_.finalHop_opt) == recipient.blindedHops)
+      assert(routes.flatMap(_.finalHop_opt).toSet == recipient.blindedHops.toSet)
       assert(routes.map(route => route2NodeIds(route)).toSet == Set(Seq(a, b), Seq(a, b, c)))
       assert(routes.map(route => route.blindedFee + route.channelFee(false)).toSet == Set(510 msat, 800 msat))
     }
@@ -586,9 +586,9 @@ class RouterSpec extends BaseRouterSpec {
       router ! RouteRequest(sender.ref, a, recipient, DEFAULT_ROUTE_PARAMS, allowMultiPart = true)
       val routes1 = sender.expectMessageType[RouteResponse].routes
       assert(routes1.length == 2)
-      router ! RouteRequest(sender.ref, a, recipient, DEFAULT_ROUTE_PARAMS, allowMultiPart = true, pendingPayments = Seq(routes1.head))
+      router ! RouteRequest(sender.ref, a, recipient, DEFAULT_ROUTE_PARAMS, allowMultiPart = true, pendingPayments = routes1.drop(1))
       val routes2 = sender.expectMessageType[RouteResponse].routes
-      assert(routes2 == routes1.tail)
+      assert(routes2 == routes1.take(1))
     }
     {
       // One blinded route is pending, we send two htlcs to the other one:
@@ -596,10 +596,11 @@ class RouterSpec extends BaseRouterSpec {
       router ! RouteRequest(sender.ref, a, recipient, DEFAULT_ROUTE_PARAMS, allowMultiPart = true)
       val routes1 = sender.expectMessageType[RouteResponse].routes
       assert(routes1.length == 2)
-      router ! RouteRequest(sender.ref, a, recipient, DEFAULT_ROUTE_PARAMS, allowMultiPart = true, pendingPayments = Seq(routes1.head))
+      router ! RouteRequest(sender.ref, a, recipient, DEFAULT_ROUTE_PARAMS, allowMultiPart = true, pendingPayments = routes1.drop(1))
       val routes2 = sender.expectMessageType[RouteResponse].routes
-      assert(routes2 == routes1.tail)
-      router ! RouteRequest(sender.ref, a, recipient, DEFAULT_ROUTE_PARAMS, allowMultiPart = true, pendingPayments = Seq(routes1.head, routes2.head.copy(amount = routes2.head.amount - 25_000.msat)))
+      assert(routes2.length == 1)
+      assert(routes2 == routes1.take(1))
+      router ! RouteRequest(sender.ref, a, recipient, DEFAULT_ROUTE_PARAMS, allowMultiPart = true, pendingPayments = routes2.head.copy(amount = routes2.head.amount - 25_000.msat) +: routes1.drop(1))
       val routes3 = sender.expectMessageType[RouteResponse].routes
       assert(routes3.length == 1)
       assert(routes3.head.amount == 25_000.msat)
@@ -611,7 +612,7 @@ class RouterSpec extends BaseRouterSpec {
       router ! RouteRequest(sender.ref, a, recipient, routeParams1, allowMultiPart = true)
       val routes1 = sender.expectMessageType[RouteResponse].routes
       assert(routes1.length == 2)
-      assert(routes1.head.blindedFee + routes1.head.channelFee(false) == 800.msat)
+      assert(routes1.map(r => r.blindedFee + r.channelFee(false)) == Seq(800 msat, 510 msat))
       val routeParams2 = DEFAULT_ROUTE_PARAMS.copy(boundaries = SearchBoundaries(1000 msat, 0.0, 6, CltvExpiryDelta(1008)))
       router ! RouteRequest(sender.ref, a, recipient, routeParams2, allowMultiPart = true, pendingPayments = Seq(routes1.head))
       sender.expectMessage(PaymentRouteNotFound(RouteNotFound))