CODEWITHSUNDEEP
rmathematical-optimizationlinear-programminglpsolve
Lasith
Lasith

Reputation: 11

How to solve linear programming problem with nxn matrix such that rows and columns sum to given values

I am trying to contract a program on R that solves for the optimal organisation of trade between 243 countries to minimise carbon emissions. I am investigating 4 types of transport - air, water, road and rail. Therefore, I want to solve the following problem:

Choose 4 matrices of trade that minimise the sum of the elements when element-wise multiplied by their emissions coefficients such that total trade is unchanged meaning that the sum of rows and columns between countries is the same as in the sample.

I have made the following code for a 3x3 example but it's not working and im not sure where else to go. I ultimately need to extend this to matrices of size 243 by 243.

# Test Emission by MOT 1 Matrix
E1 <- matrix(c(0,1,1,1,0,1,1,1,0), nrow = 3)

print(E1)

# Test Emission by MOT 2 Matrix
E2 <- matrix(c(0,2,2,2,0,2,2,2,0), nrow = 3)

print(E2)

# Test Distance between three countries matrix
D <- matrix(c(0,1,2,1,0,1,2,1,0), nrow = 3)

print(D)


objective.in <- function(values, A, B) {
  X <- matrix(values[1:9], nrow = 3, ncol = 3)
  Y <- matrix(values[10:18], nrow = 3, ncol = 3)
  return(sum(E1 * D * X + E2 * D * Y))
}

Trade_MOT1_Hypothetical <- matrix(c(0,4,6,4,0,5,2,1,0), nrow = 3)
Trade_MOT2_Hypothetical <- matrix(c(0,8,9,1,0,17,3,1,0), nrow = 3)

print(Trade_MOT1_Hypothetical)
print(Trade_MOT2_Hypothetical)

test_input <- c(Trade_MOT1_Hypothetical, Trade_MOT2_Hypothetical)

print(test_input)

print(objective.in(test_input))

# Summation matrix for the first column sum constraint

c1 <- matrix(c(1, 1, 1, 0, 0, 0, 0, 0, 0), nrow = 9)

# Summation matrix for the second column sum constraint
c2 <- matrix(c(0, 0, 0, 1, 1, 1, 0, 0, 0), nrow = 9)

# Summation matrix for the third column sum constraint
c3 <- matrix(c(0, 0, 0, 0, 0, 0, 1, 1, 1), nrow = 9)

# Summation matrix for the first row sum constraint
r1 <- matrix(c(1, 0, 0, 1, 0, 0, 1, 0, 0), nrow = 9)

# Summation matrix for the second row sum constraint
r2 <- matrix(c(0, 1, 0, 0, 1, 0, 0, 1, 0), nrow = 9)

# Summation matrix for the third row sum constraint
r3 <- matrix(c(0, 0, 1, 0, 0, 1, 0, 0, 1), nrow = 9)

const.mat <- matrix(c(r1, r2, r3, c1, c2, c3, r1, r2, r3, c1, c2, c3), nrow = 6)

print(const.mat)

const.dir <- c("=", "=", "=", "=", "=", "=")

const.rhs <- c(1000, 1000, 1000, 2000, 2000, 2000)

optimum <-  lp(direction = "min", objective.in, const.mat, const.dir, const.rhs)

optimum$solution

print(optimum$solution)

I have tried using summation matrices within the constrain matrix to apply to row and column sum constrains but this is not really working.

Upvotes: 1

Views: 150

Answers (1)

Sandipan Dey
Sandipan Dey

Reputation: 23129

Without going deep into your LP problem, it seems that you have 18 decision variables, 6 constraints and you want to solve a minimization problem, just changing your objective function to the following:

library(lpSolve)

objective.in <- c(E1*D, E2*D)
optimum <-  lp(direction = "min", objective.in, const.mat, const.dir, const.rhs)

optimum$solution
# [1] 1000    0 1000 1000    0    0    0    0 1000    0    0    0    0    0    0    0    0    0

optimum
# Success: the objective function is 3000

Is this the problem you are trying to solve? if not, can you clearly state the decision variables, constraints and the objective function you are aiming to minimize as simple math expressions?

Upvotes: 0

Related Questions