Issue

This Content is from Stack Overflow. Question asked by Pewter City

I’m trying to set up MIP problem using LpSolve and I’m at a loss on how to set it up.

We are trying to allocate resources to various investments, to maximize revenue, subject to a budget constraint. Each business is located in a particular state, and We also have to spread our allocations across 5 states (this is the one that’s causing me issues). My current linear equations are this:

Objective function: maximize following where X_i represents the number of dollars allocated to
i^th business, and R_i represents revenue generated by the i^th business

X₁ * R₁ +….+ X₃₅ * R₃₅

Subject to the constraint:

X₁ * C₁ +….+ X₃₅ * C₃₅ <= 1,000,000

Where C_i represents the costs of the i^th business. Setting this objective function and constraint matrix is very easy. However each business is located in some state, and what I need to do is setup a constraint that we must allocate to business in at least 5 states.

What I initially considered was a set of constraints where each state was represented as a row: so if this row represents the state of California for instance:

X₁ * 1 +….+ X₂ * 1 + X₃ *0 + X₃₅ * 1 <= Some Constraint

Then each business in California is assigned a value of 1, then this would give me the sum of $s (from the X_i assigned to each business) allocated to California. I could do this for all states, but that doesn’t quite get me what I want as I thought about it mroe. I could constrain each state using this methodology, but what I want is something that lets me assign Unique_States >5

But this doesn’t quite get me what I want. What I really want is something that gives me a sum of total number of states “used”.

Is this even possible?

I’ve spent a while trying to rack my brain on how to do this but I can’t quite figure it out.

There’s one other questions like this on SO, but I couldn’t follow any of the answers:
LpSolve R conditional constraint

This question is awfully similar albeit a totally different context, but I couldn’t follow it and I don’t have enough reputation to ask any questions.

If anyone could give any sort of guidance

Solution

You have 7 different patient types, x1 to x7, x’s are integers. You can select at most 2 x’s to be nonzero. You can do this by adding binary variables b1 to b7 for each x, and two constraints for each x.

x >= -U + U*b
x <= U*b

where U is some upper bound for the max x value.

library(lpSolve)

# Set coefficients of the objective function
f.obj <- c(310, 400, 500, 500, 650, 800, 850, 0, 0, 0, 0, 0, 0, 0, 0)

U=999

# Set matrix corresponding to coefficients of constraints by rows
f.con <- matrix(c(1.8, 2.8, 3, 3.6, 3.8, 4.6, 5, 0, 0, 0, 0, 0, 0, 0, 0,
                  250, 300, 500, 400, 550, 800, 750, 0, 0, 0, 0, 0, 0, 0, 0,
                  0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0,
                  1, 0, 0, 0, 0, 0, 0, -U, 0, 0, 0, 0, 0, 0, U,
                  1, 0, 0, 0, 0, 0, 0, -U, 0, 0, 0, 0, 0, 0, 0,
                  0, 1, 0, 0, 0, 0, 0, 0, -U, 0, 0, 0, 0, 0, U,
                  0, 1, 0, 0, 0, 0, 0, 0, -U, 0, 0, 0, 0, 0, 0,
                  0, 0, 1, 0, 0, 0, 0, 0, 0, -U, 0, 0, 0, 0, U,
                  0, 0, 1, 0, 0, 0, 0, 0, 0, -U, 0, 0, 0, 0, 0,
                  0, 0, 0, 1, 0, 0, 0, 0, 0, 0, -U, 0, 0, 0, U,
                  0, 0, 0, 1, 0, 0, 0, 0, 0, 0, -U, 0, 0, 0, 0,
                  0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, -U, 0, 0, U,
                  0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, -U, 0, 0, 0,
                  0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, -U, 0, U,
                  0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, -U, 0, 0,
                  0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, -U, U,
                  0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, -U, 0), nrow = 17, byrow = TRUE)

# Set unequality/equality signs
f.dir <- c("<=","<=","<=",rep(c(">=","<="),7))

# Set right hand side coefficients
f.rhs <- c(25, 4000, 2, rep(0,14))

# Final value (z)
res=lp("max", f.obj, f.con, f.dir, f.rhs, int.vec = 1:7, binary.vec = 8:14)

The results

> res$objval
[1] 4260

> res$solution
 [1] 11.000000  0.000000  0.000000  0.000000  0.000000  0.000000  1.000000  1.000000  0.000000  0.000000
[11]  0.000000  0.000000  0.000000  1.000000  0.998999

so the first and seventh patient types were selected, 11 of x1, 1 of x7.
We can check the constraints

> sum(c(1.8, 2.8, 3, 3.6, 3.8, 4.6, 5)*c(11,0,0,0,0,0,1))
[1] 24.8
> sum(c(250, 300, 500, 400, 550, 800, 750)*c(11,0,0,0,0,0,1))
[1] 3500

This Question was asked in StackOverflow by Sam and Answered by user2974951 It is licensed under the terms of CC BY-SA 2.5. - CC BY-SA 3.0. - CC BY-SA 4.0.