Optimizing Constraints for Linear Programming Problem

[alpha]

Homework Statement

Hi, trying to figure out this Linear programming problem:
A congressman of Canada is responsible for the allocation of $400000 for programs and projects in his district. It is up to the congressman to decide how to distribute the money.
The congressman has decided to allocate the money to four ongoing programs because of their importance to his district - a job training program, a parks project, a sanitation project, and a mobile library. However, the congressman wants to distribute the money in a manner that will please the most voters, or, in other words, gain him the most votes in the upcoming election. His staff's estimates of the expected number of votes gained per dollar spent for the various programs are as follows.
job training - 0.02
parks - 0.1
sanitation - 0.06
mobile library - 0.07
In order also to satisfy several local influential citizens who financed his election, he is obliged to observe the following guidelines.
None of the programs can receive more than 50% and less than 6% of the total allocation.
The amount allocated to sanitation can not exceed the total allocated to the parks and mobile library programs.
The amount allocated to job training must at least equal the amount spent on sanitation.
What is the maximal expected number of votes the congressman can gain by distributing the money among the programs?

So far I have figured out the following:

maximize 0.02x1 + 0.01x2 +0.06x3 + 0.07x4

subject to:

xi <= 200,000

xi >= 24,000

x3 <= x2 +x4

x1 >= x3

But my constraints are wrong as it is not working in solver, does anyone have any suggestions on the constraints?

Relevant Equations

So far I have figured out the following:

maximize 0.02x1 + 0.01x2 +0.06x3 + 0.07x4

subject to:

xi <= 200,000

xi >= 24,000

x3 <= x2 +x4

x1 >= x3

So far I have figured out the following:

maximize 0.02x1 + 0.01x2 +0.06x3 + 0.07x4

subject to:

xi <= 200,000

xi >= 24,000

x3 <= x2 +x4

x1 >= x3

But when I try to solve this in solver, I get an error which means my contraints must be wrong. Any suggestions on what constaints to put?

 

[BvU]

Hello @alpha,

$\qquad$ !​

Well, I get

(with 0.1 voter/dollar for parks, as in the problem statement)

So how did you set up your stuff for the solver ?

$\$

 

[Mark44]

Homework Statement:: Hi, trying to figure out this Linear programming problem:
A congressman of Canada is responsible for the allocation of $400000 for programs and projects in his district. It is up to the congressman to decide how to distribute the money.
The congressman has decided to allocate the money to four ongoing programs because of their importance to his district - a job training program, a parks project, a sanitation project, and a mobile library. However, the congressman wants to distribute the money in a manner that will please the most voters, or, in other words, gain him the most votes in the upcoming election. His staff's estimates of the expected number of votes gained per dollar spent for the various programs are as follows.
job training - 0.02
parks - 0.1
sanitation - 0.06
mobile library - 0.07
In order also to satisfy several local influential citizens who financed his election, he is obliged to observe the following guidelines.
None of the programs can receive more than 50% and less than 6% of the total allocation.
The amount allocated to sanitation can not exceed the total allocated to the parks and mobile library programs.
The amount allocated to job training must at least equal the amount spent on sanitation.
What is the maximal expected number of votes the congressman can gain by distributing the money among the programs?

But my constraints are wrong as it is not working in solver, does anyone have any suggestions on the constraints?
Relevant Equations:: So far I have figured out the following:

maximize 0.02x1 + 0.01x2 +0.06x3 + 0.07x4

subject to:
xi <= 200,000
xi >= 24,000
x3 <= x2 +x4
x1 >= x3

But when I try to solve this in solver, I get an error which means my contraints must be wrong. Any suggestions on what constaints to put?

The function you're trying to maximize has an error. Per the problem description, the expected no. of votes per dollar spent is 0.1, not 0.01. Either the problem description is wrong or the coefficient of $x_2$ in your function is wrong.

 

[alpha]

Hi, so I've been using sumproduct and individually mapping out all of the constraints on it using >= or <= depending on the constraint. I tried running this through wolfram alpha linear programming to see if my constraints are the problem, but it didnt work there either. I don't understand how these constraints worked for you can you explain how your layout compares to mine?

 

[BvU]

can you explain how your layout compares to mine?

Not really: I have no idea about your setup .
Mine is very straightforward and looks like this:

with Cell Voters =0.02*x_1+0.1*x_2+0.06*x_3+0.07*x_4
and Cell Sum24_ =x_2+x_4

C4 is x_1 etc. Note that I have cell C7 (x_4 =400000-x_1-x_2-x_3) and no need to let it be varied by the solver

$\$

 

[alpha]

The function you're trying to maximize has an error. Per the problem description, the expected no. of votes per dollar spent is 0.1, not 0.01. Either the problem description is wrong or the coefficient of $x_2$ in your function is wrong.

Hi sorry about that the voets are 0.01** not 0.1

 

[alpha]

Not really: I have no idea about your setup .
Mine is very straightforward and looks like this:

View attachment 315934

with Cell Voters =0.02*x_1+0.1*x_2+0.06*x_3+0.07*x_4
and Cell Sum24_ =x_2+x_4

C4 is x_1 etc. Note that I have cell C7 (x_4 =400000-x_1-x_2-x_3) and no need to let it be varied by the solver

$\$

Im trying to compare my notes but nothings going into be honest. I am going to sleep on it and try again tomorrow and let you know how it goes. Thank you for your input so far :)

 

[BvU]

OK,

so with Voters =0.02*x_1+0.01*x_2+0.06*x_3+0.07*x_4
it's pretty obvious mobile library wants to be at the max and parks at the minimum.
Job training doesn't yield many votes, but it has to be $\ge$ sanitation. Meaning these two split the remainder.
Oops, now I've posted the answer, a PF nono

But the answer in itself isn't interesting. What matters is why your setup doesn't work.
However, still have no idea what exactly your setup is ...

$\$

 

[alpha]

Im trying to compare my notes but nothings going into be honest. I am going to sleep on it and try again tomorrow and let you know how it goes. Thank you for your input so far :)

Hi so turns out I have to do this on spyder using PuLP not excel solver, so looks like I need to get that set up ready.

 

[alpha]

OK,

so with Voters =0.02*x_1+0.01*x_2+0.06*x_3+0.07*x_4
it's pretty obvious mobile library wants to be at the max and parks at the minimum.
Job training doesn't yield many votes, but it has to be $\ge$ sanitation. Meaning these two split the remainder.
Oops, now I've posted the answer, a PF nono

But the answer in itself isn't interesting. What matters is why your setup doesn't work.
However, still have no idea what exactly your setup is ...

$\$

Hi so I have to change my set up onto spyder using PuLP. Not sure if that is a better option since I have never used it before.
I think I have done it right on PuLp but I am not sure to be honest. Here is my code.
# -*- coding: utf-8 -*-
""""
Created on Sun Oct 23 21:03:47 2022
Votes problem from assignment

Job Trainings Parks Sanitation Mobile Library RHS

c1 0 -1 1 -1 0
c2 1 0 -1 0
c3 1 0 0 0 153000
c4 0 1 0 0 153000
c5 0 0 1 0 153000
c6 0 0 0 1 153000
c7 -1 0 0 0 -20400
c8 0 -1 0 0 -20400
c9 0 0 -1 0 -20400
c10 0 0 0 -1
votes/$ 0.04 0.09 0.05 0.03 0
max 0.04x1 + 0.09x2 + 0.05x3 + 0.03x4
s.t

xi >= 20400
xi =< 153000
x1 >= x3
x3 =< x2 + x4

@author:
"""

import pulp as pl # library with an LP Solver is named as pl
import pandas as pd

df1 = pd.read_excel('Question1.xlsx', 'Problem1', index_col=0)

# create dictionary with pairs ""product2 - price; got it from df
product = df1.loc[df1.index[-1],df1.columns[0:-1]].to_dict()

# cut off constraint matrix from dataframe; to use format Ax<=b
constraint_matrix = pd.DataFrame(
df1,index= df1.index[0:-1],columns = df1.columns[0:-1]).to_dict('index')

# use here a dictionary to loop through names of products and constraints
# get RHS associated with the constraints; dictionary: 'constraint'-rhs, from df
rhs = df1.loc[df1.index[0:-1],df1.columns[-1]].to_dict()

# ******************** MODEL ************************************************
# Creates the model which is a ""Linear Program"" with ""Max"" objective function
# any name for the model/object is fine
# defined as maximisation
model1 = pl.LpProblem('Problem 1', pl.LpMaximize)

# Creates a dictionary of variables. these are continuous varriables (default)
# use keys from the earlier defined dictionary to loop through variables later
variables = pl.LpVariable.dicts('amount', product, lowBound=0)
# add/define the objective function
model1 += pl.lpSum([product[ i]*variables[ i] for i in product])

# add constraints to the model; format like Ax<=b
for c in rhs: # notice [] in lpSum
model1 += (pl.lpSum([constraint_matrix[c][ u]*variables[ u] for u in product])
<= rhs[c], c) # c here is to name the constraints
# #specification per tonne

model1.solve() # solve the problem with the default solver

# The status of the solution is printed to the screen
print('Status:', pl.LpStatus[model1.status])

# The optimised objective function value is printed to the screen
print("Total Revenue = ", pl.value(model1.objective))

if (pl.LpStatus[model1.status] == 'Optimal'):
# Each of the variables is printed with it's resolved optimum value
for v in model1.variables():
print(v.name, '=', v.varValue)

# # # #see https://realpython.com/linear-programming-python/
# for name, constraint in model1.constraints.items():
# print(f""{name}: {constraint.value()}"")# The problem data is written to an .lp file
model1.writeLP('Mix problem.lp')

 

[alpha]

Hi so I have to change my set up onto spyder using PuLP. Not sure if that is a better option since I have never used it before.
I think I have done it right on PuLp but I am not sure to be honest. Here is my code.
# -*- coding: utf-8 -*-
""""
Created on Sun Oct 23 21:03:47 2022
Votes problem from assignment

Job Trainings Parks Sanitation Mobile Library RHS

c1 0 -1 1 -1 0
c2 1 0 -1 0
c3 1 0 0 0 153000
c4 0 1 0 0 153000
c5 0 0 1 0 153000
c6 0 0 0 1 153000
c7 -1 0 0 0 -20400
c8 0 -1 0 0 -20400
c9 0 0 -1 0 -20400
c10 0 0 0 -1
votes/$ 0.04 0.09 0.05 0.03 0
max 0.04x1 + 0.09x2 + 0.05x3 + 0.03x4
s.t

xi >= 20400
xi =< 153000
x1 >= x3
x3 =< x2 + x4

@author:
"""

import pulp as pl # library with an LP Solver is named as pl
import pandas as pd

df1 = pd.read_excel('Question1.xlsx', 'Problem1', index_col=0)

# create dictionary with pairs ""product2 - price; got it from df
product = df1.loc[df1.index[-1],df1.columns[0:-1]].to_dict()

# cut off constraint matrix from dataframe; to use format Ax<=b
constraint_matrix = pd.DataFrame(
df1,index= df1.index[0:-1],columns = df1.columns[0:-1]).to_dict('index')

# use here a dictionary to loop through names of products and constraints
# get RHS associated with the constraints; dictionary: 'constraint'-rhs, from df
rhs = df1.loc[df1.index[0:-1],df1.columns[-1]].to_dict()

# ******************** MODEL ************************************************
# Creates the model which is a ""Linear Program"" with ""Max"" objective function
# any name for the model/object is fine
# defined as maximisation
model1 = pl.LpProblem('Problem 1', pl.LpMaximize)

# Creates a dictionary of variables. these are continuous varriables (default)
# use keys from the earlier defined dictionary to loop through variables later
variables = pl.LpVariable.dicts('amount', product, lowBound=0)
# add/define the objective function
model1 += pl.lpSum([product[ i]*variables[ i] for i in product])

# add constraints to the model; format like Ax<=b
for c in rhs: # notice [] in lpSum
model1 += (pl.lpSum([constraint_matrix[c][ u]*variables[ u] for u in product])
<= rhs[c], c) # c here is to name the constraints
# #specification per tonne

model1.solve() # solve the problem with the default solver

# The status of the solution is printed to the screen
print('Status:', pl.LpStatus[model1.status])

# The optimised objective function value is printed to the screen
print("Total Revenue = ", pl.value(model1.objective))

if (pl.LpStatus[model1.status] == 'Optimal'):
# Each of the variables is printed with it's resolved optimum value
for v in model1.variables():
print(v.name, '=', v.varValue)

# # # #see https://realpython.com/linear-programming-python/
# for name, constraint in model1.constraints.items():
# print(f""{name}: {constraint.value()}"")# The problem data is written to an .lp file
model1.writeLP('Mix problem.lp')

the question was also altered by the prof so I have updated that as well. Sorry for not mentioning

 

[BvU]

Had to look up "spyder pulp" to find out this is python-ish. Interesting IDE, thanks for mentioning it !
Can read rudimentary python, but this is a bit more than that

No idea what's going on. What comes out ? Crash, wrong answer, ... ?

the question was also altered by the prof

What's changed ?

$\$

 

[alpha]

Had to look up "spyder pulp" to find out this is python-ish. Interesting IDE, thanks for mentioning it !
Can read rudimentary python, but this is a bit more than that

No idea what's going on. What comes out ? Crash, wrong answer, ... ?What's changed ?

$\$

The number of votes per dollar and the constraints. It doesn't crash but I am not sure the code I've posted above is correct since I've used different sources to figure it out so needed some guidance on the legibility of the code and if I am in the right direction or need drastic changes to my approach

 

[Mark44]

@alpha, I edited the code in post 10 because your use of indexes i and u within brackets gets rendered by browsers as BBCode for italics and underscore.

I modified it by changing [i] and [u] to [ i] and [ u]. IOW, by adding a space between the left bracket and the character inside.