"""Implements a fast dual formulation."""fromsympy.core.singletonimportSfrommicom.loggerimportlogger
[docs]deffast_dual(model,prefix="dual_"):"""Add dual formulation to the problem. A mathematical optimization problem can be viewed as a primal and a dual problem. If the primal problem is a minimization problem the dual is a maximization problem, and the optimal value of the dual is a lower bound of the optimal value of the primal. For linear problems, strong duality holds, which means that the optimal values of the primal and dual are equal (duality gap = 0). This functions takes an optlang Model representing a primal linear problem and returns a new Model representing the dual optimization problem. The provided model must have a linear objective, linear constraints and only continuous variables. Furthermore, the problem must be in standard form, i.e. all variables should be non-negative. Both minimization and maximization problems are allowed. Attributes ---------- model : cobra.Model The model to be dualized. prefix : str The string that will be prepended to all variable and constraint names in the returned dual problem. Returns ------- dict The coefficients for the new dual objective. """logger.info("adding dual variables")iflen(model.variables)>1e5:logger.warning("the model has a lot of variables,""dual optimization will be extremely slow :O")prob=model.problemmaximization=model.objective.direction=="max"ifmaximization:sign=1else:sign=-1coefficients={}dual_objective={}to_add=[]# Add dual variables from primal constraints:forconstraintinmodel.constraints:ifconstraint.expression==0:continue# Skip empty constraintifnotconstraint.is_Linear:raiseValueError("Non-linear problems are not supported: "+str(constraint))ifconstraint.lbisNoneandconstraint.ubisNone:logger.debug("skipped free constraint %s"%constraint.name)continue# Skip free constraintifconstraint.lb==constraint.ub:const_var=prob.Variable(prefix+constraint.name+"_constraint",lb=None,ub=None)to_add.append(const_var)ifconstraint.lb!=0:dual_objective[const_var.name]=sign*constraint.lbcoefs=constraint.get_linear_coefficients(constraint.variables)forvariable,coefincoefs.items():coefficients.setdefault(variable.name,{})[const_var.name]=sign*coefelse:ifconstraint.lbisnotNone:lb_var=prob.Variable(prefix+constraint.name+"_constraint_lb",lb=0,ub=None)to_add.append(lb_var)ifconstraint.lb!=0:dual_objective[lb_var.name]=-sign*constraint.lbifconstraint.ubisnotNone:ub_var=prob.Variable(prefix+constraint.name+"_constraint_ub",lb=0,ub=None)to_add.append(ub_var)ifconstraint.ub!=0:dual_objective[ub_var.name]=sign*constraint.ubifnot(constraint.expression.is_Addorconstraint.expression.is_Mul):raiseValueError("Invalid expression type: "+str(type(constraint.expression)))ifconstraint.expression.is_Add:coefficients_dict=constraint.get_linear_coefficients(constraint.variables)else:# constraint.expression.is_Mul:args=constraint.expression.argscoefficients_dict={args[1]:args[0]}forvariable,coefincoefficients_dict.items():ifconstraint.lbisnotNone:coefficients.setdefault(variable.name,{})[lb_var.name]=(-sign*coef)ifconstraint.ubisnotNone:coefficients.setdefault(variable.name,{})[ub_var.name]=(sign*coef)# Add dual variables from primal boundsforvariableinmodel.variables:ifnotvariable.type=="continuous":raiseValueError("Integer variables are not supported: "+str(variable))ifvariable.lbisnotNoneandvariable.lb<0:raiseValueError("Problem is not in standard form ("+variable.name+" can be negative)")ifvariable.lb>0:bound_var=prob.Variable(prefix+variable.name+"_lb",lb=0,ub=None)to_add.append(bound_var)coefficients.setdefault(variable.name,{})[bound_var.name]=-signdual_objective[bound_var.name]=-sign*variable.lbifvariable.ubisnotNone:bound_var=prob.Variable(prefix+variable.name+"_ub",lb=0,ub=None)to_add.append(bound_var)coefficients.setdefault(variable.name,{})[bound_var.name]=signifvariable.ub!=0:dual_objective[bound_var.name]=sign*variable.ubmodel.add_cons_vars(to_add)# Add dual constraints from primal objectiveprimal_objective_dict=model.objective.get_linear_coefficients(model.objective.variables)forvariableinmodel.objective.variables:obj_coef=primal_objective_dict[variable]ifmaximization:const=prob.Constraint(S.Zero,lb=obj_coef,name=prefix+variable.name)else:const=prob.Constraint(S.Zero,ub=obj_coef,name=prefix+variable.name)model.add_cons_vars([const])model.solver.update()coefs={model.variables[vid]:coefforvid,coefincoefficients[variable.name].items()}const.set_linear_coefficients(coefs)# Make dual objectivecoefs={model.variables[vid]:coefforvid,coefindual_objective.items()ifcoef!=0}logger.info("dual model has {} terms in objective".format(len(coefs)))returncoefs