When htlc min breaks renepay

[Lagrang3]

I came up with the following test case for renepay:

def test_htlc_minmax(node_factory):
    """
    Topology:
    1----2----4
    |         |
    3----5----6

    Try sending a payment from 1 to 6, there are two routes
    1->2->4->6 and 1->3->5->6.
    The route 1->2->4->6 contains a channel with
    htlcmin=htlcmax=X but 0 routing fees, the other path has high routing fees.
    The optimal solution sends n*X along 1->2->4->6 and the rest through
    1->3->5->6.
    """
    opts = [
        {"disable-mpp": None, "fee-base": 0, "fee-per-satoshi": 0},#1
        {"disable-mpp": None, "fee-base": 0, "fee-per-satoshi": 0},#2
        {"disable-mpp": None, "fee-base": 1000, "fee-per-satoshi": 1000},#3
        {"disable-mpp": None, "fee-base": 0, "fee-per-satoshi": 0},#4
        {"disable-mpp": None, "fee-base": 1000, "fee-per-satoshi": 1000},#5
        {"disable-mpp": None, "fee-base": 0, "fee-per-satoshi": 0},#6
    ]
    l1, l2, l3, l4, l5, l6 = node_factory.get_nodes(6, opts=opts)
    channels = start_channels(
        [
            (l1, l2, 1000000),
            (l2, l4, 1000000),
            (l4, l6, 1000000),
            (l1, l3, 1000000),
            (l3, l5, 1000000),
            (l5, l6, 1000000),
        ]
    )
    htlc_max = 100100000
    htlc_min =  99900000
    l4.rpc.setchannel(l6.info["id"], htlcmin=htlc_min, htlcmax=htlc_max)
    l6.rpc.setchannel(l4.info["id"], htlcmin=htlc_min, htlcmax=htlc_max)
    scid = l4.get_channel_scid(l6)
    wait_for(
        lambda: [c["htlc_minimum_msat"] for c in l1.rpc.listchannels(scid)["channels"]]
        == [htlc_min, htlc_min]
    )
    wait_for(
        lambda: [c["htlc_maximum_msat"] for c in l1.rpc.listchannels(scid)["channels"]]
        == [htlc_max, htlc_max]
    )

    # 200000sat (circa) go through 1->2->4->6
    # 50000sat (circa) go through 1->3->5->6
    amt = "250000sat"

    # in the worst case we send 2*99900sat through 1->2->4->6 at 0 fees and the
    # rest 50200sat through 1->3->5->6, paying in total 102451msat in fees.
    worst_case = "250102451msat"

    inv = l6.rpc.invoice(amt, "inv", "description")

    response = l1.rpc.call("renepay", {"invstring": inv["bolt11"]})
    l1.wait_for_htlcs()
    invoice = only_one(l6.rpc.listinvoices("inv")["invoices"])
    assert invoice["amount_received_msat"] >= Millisatoshi(amt)

    # This test would fail if all 250000sat go through 1->3->5->6 paying
    # 502251msat in fees or more.
    assert response["amount_sent_msat"] <= Millisatoshi(worst_case)

The idea is to break renepay's optimality by exploiting a constraint the Min Cost Flow (MCF) algorithm cannot handle. That is, htlc_maximum can be taken into account either by limiting the flow capacity or the arcs, or when dissecting flows into routes. But htlc_minimum has, at least to my knowledge, no way to be set as a constrain in the solver. The htlc_minimum constraint must be taken into account after MCF computation.

Currently in this situation renepay will determine the best route is 1->2->4->6 and since there is an htlc_maximum constraint there, it will construct 3 different payment routes with 100000sat, 100000sat and 50000sat using the same path. Before sendpay is called, the plugin will determine that 50000sat is smaller than htlc_minimum for channel 4->6 and that channel will be flagged as disabled, then MCF will be called again and then the entire payment will be sent through 1->3->5->6, when it would have sufficed to send 50000sat through 1->3->5->6.