Skip to content
Advertisement

Get minimum of maximize value on pulp objective function

I’m trying to use pulp to get minimum value U(X) of following objective function, objective function

where x_{f,i,v} is binary value.

And I’m having problem while writing max() when set an objective function to pulp.LpProblem.

What I do is use python inner function max() but it gives me an error. Seems like it cannot be used to pulp.

    for each_sfc in self.SFCs:
        vnf_id_list = list()
        for each_VNF in each_sfc.VNF_list:
            vnf_id_list.append(str(each_VNF.ID))

        new_sfc_vars = LpVariable.dicts(
            name='X',
            indexs=vnf_id_list,
            lowBound=0,
            upBound=1,
            cat='Continuous'
        )

        for each_key in new_sfc_vars.keys():
            new_sfc_vars[each_key] = 1 - new_sfc_vars[each_key]

        self.sfc_vars.append(new_sfc_vars)

    self.LP_model = LpProblem(
        name="Static backup",
        sense=LpMinimize
    )

    for each_SFC, each_vars in zip(self.SFCs, self.sfc_vars):
        self.LP_model.objective += each_SFC.backup_cost * max(each_vars.values())
    print(self.LP_model.objective)

How can I use max() with pulp or how can I reformulate the code?

Advertisement

Answer

This is a very basic question.

  1. max() is not linear. Linear expressions look like a1*x1+a2*x2+.... PuLP is for linear models only, so it only allows linear expressions in the objective and the constraints. Note that some modeling tools have a max function, but they typically linearize this under the hood.

  2. A very standard formulation for a construct like min sum(i, max(j, x(i,j)) is

    min sum(i, y(i))
    y(i) >= x(i,j)  for all i,j 
    
  3. Just consult any LP textbook. It will explain this formulation. Often this is called minimax.

Advertisement