CODEWITHSUNDEEP
pythonnumpyoptimizationlinear-programmingcvxpy
Cino
Cino

Reputation: 93

largest and others constraints in portfolio optimization (MILP problem) CVXPY

Here is python code in cvxpy:

import numpy as np
import time
import cvxpy as cp
n = 10

a = np.random.randint(1, 10, size=n)

b = np.random.randint(1, 10, size=n)
c = np.random.randint(1, 10, size=n)
d = np.random.randint(1, 10, size=n)

x = cp.Variable(shape=n, boolean=True)

# objective function 
objective = cp.Maximize(cp.sum(cp.multiply(x,a)))

# constraints
constraints = []
constraints.append(cp.sum(cp.multiply(x, b) <= 50) # constraint 1
constraints.append(cp.sum_largest(cp.hstack([
    cp.sum(cp.multiply(x, b)), 
    cp.sum(cp.multiply(x, c)), 
    cp.sum(cp.multiply(x, d))]), 2) <= 100) # constraint 2

prob = cp.Problem(objective, constraints)
# solve model
prob.solve(solver=cp.CBC, verbose=False, maximumSeconds=100)
print("status:", prob.status)

a, b, c, d and x are all binary. The objective is max(sum(x*a)) and the constraints are:

  1. sum(x*b) <= 50

  2. sum of the largest 2 values in [sum(x*b), sum(x*c), sum(x*d)] <= 100, this is implemented via sum_largest sum_largest([x*a, x*b, x*c], 2) <= 100

  3. define others=[b, c, d] - b - (largest 2 value in [b, c, d])

    For example:

    case1: [sum(x*b), sum(x*c), sum(x*d)] = [1,2,3], so (largest 2 value in [b, c, d]) = [c, d] and others=[b, c, d] - b - [c, d] = None

    case2: [sum(x*b), sum(x*c), sum(x*d)] = [3,2,1], so (largest 2 value in [b, c, d]) = [b, c] and others=[b, c, d] - b - [b, c] = d

    constriants:

    for i in others:
 constraints.append(cp.sum(cp.multiply(x, i) <= 10)

Constraints 1, 2 have already been implemented. How can I implement constraint 3? Is it even possible in cvxpy?

Upvotes: 0

Views: 229

Answers (1)

Erwin Kalvelagen
Erwin Kalvelagen

Reputation: 16724

Note: the question has changed, so this is no longer a valid answer.

The original problem was:

(1) sum(x*b) <= 5 
(2) max([sum(x*b), sum(x*c), sum(x*d)]) <= 10 
(3) define others=[b, c, d] - b - maxBCD([b, c, d]) (others is a set of symbols, maxBCD returns a symbol)
    for i in others:  
         constraints.append(cp.sum(cp.multiply(x, i) <= 1)

This is an answer to that original problem statement. I have not deleted the answer as it is a good starting point (also because the answer states the problem a bit more precisely: in mathematical terms).

(1) and (2) can be written as:

  xb = sum(x*b)
  xc = sum(x*c)
  xd = sum(x*d)

  xb <= 5
  xc <= 10
  xd <= 10

(3) needs to know which one is the maximum. I assume two or all three can be maximum.

   bIsMax,cIsMax,dIsMax: binary variables
    
   # bisMax=1 => xb is largest
   xb >= xc - (1-bisMax)*10
   xb >= xd - (1-bisMax)*10
   # cisMax=1 => xc is largest
   xc >= xb - (1-cisMax)*5
   xc >= xd - (1-cisMax)*10
   # disMax=1 => xd is largest
   xd >= xb - (1-disMax)*5
   xd >= xc - (1-disMax)*10
   # at least one of them is largest
   bIsMax + cIsMax + dIsMax >= 1

Note that others=[b, c, d] - b- maxBCD can be restated as: others=[c, d] - maxBCD.

   # if c is not max then xc<=1
   xc <= 1 + 9*cIsMax
   # if d is not max then xd<=1
   xd <= 1 + 9*dIsMax

Left to the reader:

  1. check the math and implement in CVXPY.
  2. update the answer to the revised question.

Upvotes: 1

Related Questions