Python linear programming - how to constrain a variable to be an integer

Question

I would like to maximize the probability of winning a raffle by buying a certain number of tickets. For this, I wrote the following code

import numpy as np
import math as mt
from scipy.optimize import minimize
from pulp import *

def objective(tickets, winners = 500, losers = 2500, cost_of_ticket = 40, winning_amt = 1000):

    Pwin = 1 - mt.factorial(losers)//mt.factorial(losers - tickets)*mt.factorial(winners+losers-tickets)/mt.factorial(winners+losers)
    Ewin = Pwin*(winning_amt - cost_of_ticket*tickets)

    return Ewin


# declare your variables
tickets = LpVariable("tickets", range(0, 10))   # 0<= tickets <= 10

prob = LpProblem("problem", LpMaximize)

#define the objective
prob += objective(tickets)

# solve the problem
status = prob.solve(GLPK(msg=0))
LpStatus[status]

# print the results
value(tickets)

The issue seems to be that the number of tickets that get passed into the objective function is not an integer (and the factorial function then fails). Can anyone suggest how I should ensure that the ticket is restricted to positive integer values?

The answer, for checking, should be 8. I can do this by manually calling the objective function and checking.

Well, the obvious way is to transform it to an integer by calling int() on the value. Is there a reason you can't do that? — John Gordon
– John Gordon, Commented Nov 17, 2017 at 3:21
Sorry, I'm a bit new to this - but where should I make it an integer? In the objective function or when I declare "tickets" as an LpVariable? — user1936752
– user1936752, Commented Nov 17, 2017 at 3:24
You need to declare it when defining the variable like explained here. On top of that i'm really not sure if your function-based approach will work here, but it's hard to tell. — sascha
– sascha, Commented Nov 17, 2017 at 3:29
If tickets is an object of type LpVariable how can you do something like: losers - tickets what's the meaning of an integer minus an object ? — Nir Alfasi
– Nir Alfasi, Commented Nov 17, 2017 at 3:31
I see - I haven't used scipy either but I would like to retain the ability to keep the objective as a function and modify it as I need. Could you suggest a general way to proceed to maximize such a function? — user1936752
– user1936752, Commented Nov 17, 2017 at 3:32

Erwin Kalvelagen · Accepted Answer · 2017-11-17 20:55:05Z

1

Your objective is really

 ExpWin(t) = choose(N,t)*(A-C*t)

where t is an integer variable and N,A,C are constants. This is a nonlinear function so a linear MIP solver will not be able to handle this.

For this problem it is silly, but in general we can linearize this. Introduce binary variables x(i) with:

x(i) = 1 if tickets=i
       0 otherwise

This can be enforced by

sum(i,x(i)) = 1
sum(i,i*x(i)) = tickets

This only makes sense if the range of variable tickets is small (in your case 10). Now we can precalculate a constant array w(i) which is the expected win if the number of tickets is i. Now the objective can look like:

max sum(i, w(i)*x(i))

which is now linear.

Anyway it is always a good idea to step away from code and write down the problem in math. This can help you think about the problem in a different way.

edited Nov 17, 2017 at 20:55

answered Nov 17, 2017 at 20:49

Erwin Kalvelagen

16.9k3 gold badges17 silver badges42 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Flexecute · Accepted Answer · 2017-11-27 01:04:59Z

0

You can restrict a variable to integers when you define it:

tickets = LpVariable("tickets", range(0, 10), cat='Integer') # 0<= tickets <= 10

As per sascha's comment, this is explained here

answered Nov 27, 2017 at 1:04

Flexecute

1061 silver badge6 bronze badges

Collectives™ on Stack Overflow

Python linear programming - how to constrain a variable to be an integer

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related