1
$\begingroup$

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!

$\endgroup$
2
  • 2
    $\begingroup$ This is more a modeling problem than a PuLP specific problem. I suggest you write your mathematical model first, so that the community can try and help you with the formulation of the missing constraints. $\endgroup$
    – Kuifje
    Apr 13, 2023 at 8:27
  • $\begingroup$ @Kuifje good point. As I said I'm fairly new to this; I tend to approach these problems software first which I think is part of a broader underlying problem. I will try to formulate the mathematical model for this post when I have a chance, and will keep your advice in mind if I have future questions. $\endgroup$
    – 3Li
    Apr 13, 2023 at 20:52

3 Answers 3

2
$\begingroup$

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..

$\endgroup$
5
  • $\begingroup$ This is too restrictive when $x_{at}=0$ or $x_{dt}=0$. You can correct it by disaggregating $\sum_l$. $\endgroup$
    – RobPratt
    Apr 13, 2023 at 12:29
  • $\begingroup$ Better, but the first constraint should be only for $l\not= a$ and the second constraint only for $l \not= d$. $\endgroup$
    – RobPratt
    Apr 13, 2023 at 13:19
  • $\begingroup$ I just combined these two hoping the OP will get it $\endgroup$ Apr 13, 2023 at 13:21
  • $\begingroup$ Looks good now. +1 $\endgroup$
    – RobPratt
    Apr 13, 2023 at 13:26
  • 1
    $\begingroup$ Thank you @Sutanu that does the trick. It took me a bit to understand, I think it might be helpful to specify that each expression is for all dates (i.e. $\forall t \in T$) in addition to all locations (excluding $a$ and $d$ respectively) as you posted. $\endgroup$
    – 3Li
    Apr 14, 2023 at 2:21
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.