How to make limited bundling constraint in variable selection for maximization problem

Question

I am working on a revenue maximization problem out of a price time series by selecting a number of hours.

The constraint is that you can select # of chances In each chance, you can choose up to # of consecutive hours. Hence, the maximum, selected hours equals '# of chance' * '# of consecutive hours to choose'

For example, in 24 hours, you have up to 3 chances and you have up to 3 consecutive hours for each chance The total selected hours can be up to 9 hours

When the prices series is something like this,

Then the optimally selected hours are: (3, 4, 5), (10, 11, 12), (17, 18, 19)

In Pyomo, I have created a code up to general constraints

I would like to create an additional constraint for :: In each chance, you can choose up to # of consecutive hours.

and I wonder whether you have any ideas about the answer.

Your answer can be in general math formula, pyomo, GAMS, or any math programming language you like.

Answer 1

I think this will work for you. I created a secondary "helper" variable to annotate the period start selections and used it to constrain which segments were "up"

With this structure, the constraints become a little clearer. One constraint to limit the number of period starts. Another enforcing the window around that selection.

# price period selector
import pyomo.environ as pe

prices = [1,1,10,10,10,1,1,1,1,20,20,20,1,1,1,1,30,30,30,1,1,1,1,1]
price_dict = {idx: p for idx, p in enumerate(prices)}

dispatch=3
max_up_time=3

m = pe.ConcreteModel()

# sets
m.TIME = pe.Set(initialize=range(len(prices)))

# params
m.P = pe.Param(m.TIME, initialize=price_dict)

# variables
m.u = pe.Var(m.TIME, domain=pe.Boolean)  # true if that period is "on"

# make a second variable, which holds the selected start times
m.selected = pe.Var(m.TIME, domain=pe.Boolean)


###  OBJ  ###
m.OBJ = pe.Objective(expr=sum(m.u[t] * m.P[t] for t in m.TIME), sense=pe.maximize)

###  Constraints  ###

# limit selection of period starts
m.C1 = pe.Constraint(expr=sum(m.selected[t] for t in m.TIME) <= dispatch)

# continuity constraint.  Any "up" segment must be preceeded by a "selection" within window
# this is a lookback constraint.
def continuity(model, t):
    return sum(m.selected[tt] for tt in range(max(t - max_up_time + 1, 0), t+1)) >= m.u[t]  
m.C2 = pe.Constraint(m.TIME, rule=continuity)

# m.pprint()

solver = pe.SolverFactory('cbc')
result = solver.solve(m)

m.display()

Yields:

  Variables:
    u : Size=24, Index=TIME
        Key : Lower : Value : Upper : Fixed : Stale : Domain
          0 :     0 :   0.0 :     1 : False : False : Boolean
          1 :     0 :   0.0 :     1 : False : False : Boolean
          2 :     0 :   1.0 :     1 : False : False : Boolean
          3 :     0 :   1.0 :     1 : False : False : Boolean
          4 :     0 :   1.0 :     1 : False : False : Boolean
          5 :     0 :   0.0 :     1 : False : False : Boolean
          6 :     0 :   0.0 :     1 : False : False : Boolean
          7 :     0 :   0.0 :     1 : False : False : Boolean
          8 :     0 :   0.0 :     1 : False : False : Boolean
          9 :     0 :   1.0 :     1 : False : False : Boolean
         10 :     0 :   1.0 :     1 : False : False : Boolean
         11 :     0 :   1.0 :     1 : False : False : Boolean
         12 :     0 :   0.0 :     1 : False : False : Boolean
         13 :     0 :   0.0 :     1 : False : False : Boolean
         14 :     0 :   0.0 :     1 : False : False : Boolean
         15 :     0 :   0.0 :     1 : False : False : Boolean
         16 :     0 :   1.0 :     1 : False : False : Boolean
         17 :     0 :   1.0 :     1 : False : False : Boolean
         18 :     0 :   1.0 :     1 : False : False : Boolean
         19 :     0 :   0.0 :     1 : False : False : Boolean
         20 :     0 :   0.0 :     1 : False : False : Boolean
         21 :     0 :   0.0 :     1 : False : False : Boolean
         22 :     0 :   0.0 :     1 : False : False : Boolean
         23 :     0 :   0.0 :     1 : False : False : Boolean
    selected : Size=24, Index=TIME
        Key : Lower : Value : Upper : Fixed : Stale : Domain
          0 :     0 :   0.0 :     1 : False : False : Boolean
          1 :     0 :   0.0 :     1 : False : False : Boolean
          2 :     0 :   1.0 :     1 : False : False : Boolean
          3 :     0 :   0.0 :     1 : False : False : Boolean
          4 :     0 :   0.0 :     1 : False : False : Boolean
          5 :     0 :   0.0 :     1 : False : False : Boolean
          6 :     0 :   0.0 :     1 : False : False : Boolean
          7 :     0 :   0.0 :     1 : False : False : Boolean
          8 :     0 :   0.0 :     1 : False : False : Boolean
          9 :     0 :   1.0 :     1 : False : False : Boolean
         10 :     0 :   0.0 :     1 : False : False : Boolean
         11 :     0 :   0.0 :     1 : False : False : Boolean
         12 :     0 :   0.0 :     1 : False : False : Boolean
         13 :     0 :   0.0 :     1 : False : False : Boolean
         14 :     0 :   0.0 :     1 : False : False : Boolean
         15 :     0 :   0.0 :     1 : False : False : Boolean
         16 :     0 :   1.0 :     1 : False : False : Boolean
         17 :     0 :   0.0 :     1 : False : False : Boolean
         18 :     0 :   0.0 :     1 : False : False : Boolean
         19 :     0 :   0.0 :     1 : False : False : Boolean
         20 :     0 :   0.0 :     1 : False : False : Boolean
         21 :     0 :   0.0 :     1 : False : False : Boolean
         22 :     0 :   0.0 :     1 : False : False : Boolean
         23 :     0 :   0.0 :     1 : False : False : Boolean

  Objectives:
    OBJ : Size=1, Index=None, Active=True
        Key  : Active : Value
        None :   True : 180.0

  Constraints:
    C1 : Size=1
        Key  : Lower : Body : Upper
        None :  None :  3.0 :   3.0
    C2 : Size=24
        Key : Lower : Body : Upper
          0 :  None :  0.0 :   0.0
          1 :  None :  0.0 :   0.0
          2 :  None :  0.0 :   0.0
          3 :  None :  0.0 :   0.0
          4 :  None :  0.0 :   0.0
          5 :  None :  0.0 :   0.0
          6 :  None :  0.0 :   0.0
          7 :  None :  0.0 :   0.0
          8 :  None :  0.0 :   0.0
          9 :  None :  0.0 :   0.0
         10 :  None :  0.0 :   0.0
         11 :  None :  0.0 :   0.0
         12 :  None :  0.0 :   0.0
         13 :  None :  0.0 :   0.0
         14 :  None :  0.0 :   0.0
         15 :  None :  0.0 :   0.0
         16 :  None :  0.0 :   0.0
         17 :  None :  0.0 :   0.0
         18 :  None :  0.0 :   0.0
         19 :  None :  0.0 :   0.0
         20 :  None :  0.0 :   0.0
         21 :  None :  0.0 :   0.0
         22 :  None :  0.0 :   0.0
         23 :  None :  0.0 :   0.0
[Finished in 3.6s]