PuLP ensure first and last choice

Question

I have an assignment problem where I have $N$ locations and $M$ dates for each location, and the goal is to choose $K$ location-date pairs that maximize revenue. There are a number of constraints, for example a location can only be chosen once, a date can only be chosen once, etc.

Here is a dummy example of how I'm setting up the problem in PuLP:

import random
import pulp as pl


# Dummy revenue calculation
def get_revenue(location, date):
    return random.randint(100, 1000)


def optimize(max_choices=4):
    # Dummy data
    locations = ['a', 'b', 'c', 'd']
    dates = ['2023-01-01', '2023-02-01', '2023-03-01', '2024-04-01']

    prob = pl.LpProblem('RevenueMaximization', pl.LpMaximize)

    # Variable setup
    pairs = [(location, date) for location in locations for date in dates]
    choices = pl.LpVariable.dicts('LocationDates', pairs, cat=pl.LpBinary)

    # Objective function
    prob += pl.lpSum([choices[pair]*get_revenue(pair[0], pair[1]) for pair in pairs])

    # Desired choices constraint
    prob += pl.lpSum([choices[pair] for pair in pairs]) == max_choices, 'MaxChoices'

    # One date per location constraint
    for location in locations:
        prob += pl.lpSum([
            choices[(location, date)]
            for date in dates
        ]) <= 1, f'OneDatePerLocation_{location}'

    # One location per date constraint
    for date in dates:
        prob += pl.lpSum([
            choices[(location, date)]
            for location in locations
        ]) <= 1, f'OneLocationPerDate_{date}'
        
    # Other constraints...

    # Solve and print results
    prob.solve()
    if pl.LpStatus[prob.status] == 'Optimal':
        for v in prob.variables():
            if v.value() > 0:
                print(v.name, '=', v.dj)
    else:
        print('Problem is infeasible')


if __name__ == '__main__':
    optimize()

This works fine, but there are two constraints that I have left out that are stumping me. I want to allow a user to specify a first and/or last location, meaning if a user selects a as the first location, then no other location can have a date earlier than the date chosen for a. Similarly, if a user selects d as the last location, then no locations can have a date after the date chosen for d.

In the real world, I have a few thousand locations and a dynamic range of dates that spans ~1.5 years, so I think brute forcing is out of the equation. I'd like to solve these constraints directly with PuLP, but I am having trouble wrapping my head around how to formulate, let alone implement them.

I am fairly new to linear programming and using PuLP, so I'm not sure if there is some trick I'm missing, or if this is complicated and requires additional indicator variables. Any help would be greatly appreciated!

Answer 1

Additional constraints
$ \sum_{k=1}^{t-1} x_{l,k} \le 1-x_{a,t} \quad \forall l \neq a$
$\sum_{k=t+1}^{T} x_{l,k} \le 1-x_{d,t} \quad \forall l \neq d$
where $x$ is the binary location pair variable as you defined & $t$ is the index over chronologically sorted list of dates with $T$ as the last index.

Corrected..

Answer 2

For anyone who comes across this in the future and is looking to translate the solution @Sutanu posted to PuLP, here is how I implemented it.

import random
import pulp as pl


# Dummy revenue calculation
def get_revenue(location, date):
    return random.randint(100, 1000)


def optimize(first_location, last_location, max_choices=4):
    # Dummy data
    locations = ['a', 'b', 'c', 'd']
    dates = ['2022-12-01', '2023-01-01', '2023-02-01', '2023-03-01', '2023-04-01', '2023-05-01', '2023-06-01']

    prob = pl.LpProblem('RevenueMaximization', pl.LpMaximize)

    # Variable setup
    pairs = [(location, date) for location in locations for date in dates]
    choices = pl.LpVariable.dicts('LocationDates', pairs, cat=pl.LpBinary)

    # Objective function
    prob += pl.lpSum([choices[pair] * get_revenue(pair[0], pair[1]) for pair in pairs])

    # Desired choices constraint
    prob += pl.lpSum([choices[pair] for pair in pairs]) == max_choices, 'MaxChoices'

    # One date per location constraint
    for location in locations:
        prob += pl.lpSum([
            choices[(location, date)]
            for date in dates
        ]) <= 1, f'OneDatePerLocation_{location}'

    # One location per date constraint
    for date in dates:
        prob += pl.lpSum([
            choices[(location, date)]
            for location in locations
        ]) <= 1, f'OneLocationPerDate_{date}'

    # First location constraint
    for location in filter(lambda x: x != first_location, locations):
        for idx, date in enumerate(dates):
            prob += pl.lpSum([
                choices[(location, d)]
                for d in dates[:idx]
            ]) <= 1 - choices[(first_location, date)], f'FirstLocationExclude_{location}_{date}'

    # Last location constraint
    for location in filter(lambda x: x != last_location, locations):
        for idx, date in enumerate(dates):
            prob += pl.lpSum([
                choices[(location, d)]
                for d in dates[idx:]
            ]) <= 1 - choices[(last_location, date)], f'LastLocationExclude_{location}_{date}'

    # Solve and print results
    prob.solve()
    if pl.LpStatus[prob.status] == 'Optimal':
        for v in prob.variables():
            if v.value() > 0:
                print(v.name, '=', v.dj)
    else:
        print('Problem is infeasible')


if __name__ == '__main__':
    optimize(first_location='a', last_location='d')

Note that the range of dates is expanded from the original question to show that the constraints work for larger solution spaces. It also assumes that dates is in chronological order, which helps avoid any datetime conversions or comparisons.

It's definitely a toy example, but it should illustrate the core concepts.

Answer 3

Here’s a somewhat automated way to obtain the formulation proposed by @Sutanu. You want to enforce the logical implication $$\bigwedge_t \left(x_{at} \implies \bigwedge_{l\not= a}\bigwedge_{k<t}\lnot x_{lk}\right).$$ Rewriting in conjunctive normal form yields $$ \bigwedge_t \left(\lnot x_{at} \lor \bigwedge_{l\not= a}\bigwedge_{k<t}\lnot x_{lk}\right) \\ \bigwedge_t \bigwedge_{l\not= a}\bigwedge_{k<t}\left( \lnot x_{at} \lor \lnot x_{lk}\right)\\ \bigwedge_t \bigwedge_{l\not= a}\bigwedge_{k<t}\left( (1-x_{at}) + (1-x_{lk})\ge 1 \right)\\ \bigwedge_t \bigwedge_{l\not= a}\bigwedge_{k<t}\left(x_{at} + x_{lk}\le 1 \right) $$ This is correct but can be strengthened by using the fact that $\sum_k x_{lk}\le 1$, as shown here. The strengthened constraints are $$\bigwedge_t \bigwedge_{l\not= a}\left(x_{at} + \sum_{k<t} x_{lk}\le 1 \right). $$ The constraints for $x_{dt}$ have a similar derivation.