objectives.h

Go to the documentation of this file.

#ifndef LINE_OPT_OBJECTIVES_H
#define LINE_OPT_OBJECTIVES_H
 
/**
 * @file
 * @ingroup line_opt
 * The objectives to minimize and the constraints to respect.
 *
 * A `Constraint` returns its VIOLATION, not a boolean: zero when satisfied and
 * the amount by which it is breached otherwise, so a search can follow the
 * gradient of an infeasible point back into the feasible region. An
 * unobtainable metric gives infinity rather than zero, so a model that failed to
 * solve cannot read as feasible. `ResponseTimeConstraint`,
 * `SystemResponseTimeConstraint`, `ThroughputConstraint` and
 * `UtilizationConstraint` read the solved model; `BudgetConstraint` reads the
 * variable values instead, costing each by a per-variable rate.
 *
 * An `Objective` carries its own constraint list, and
 * `evaluate_with_penalty` folds the violations in at a weight (default 1e6),
 * which is how the derivative-free solvers handle constraints. Every objective
 * is a MINIMIZATION: `MaximizePerformance` returns the negated score.
 *
 * Formatting note: the class bodies here are written one per line, unlike the
 * rest of the tree.
 */
#include <algorithm>
#include <cmath>
#include <memory>
#include <string>
#include <vector>
#include "line/opt/results.h"
namespace line { namespace opt {
class Constraint{public:explicit Constraint(std::string n=""):name_(std::move(n)){}virtual~Constraint()=default;virtual double evaluate(const EvaluationResult&,const VariableValues&)const=0;virtual std::string generated_name()const=0;std::string name()const{return name_.empty()?generated_name():name_;}bool satisfied(const EvaluationResult&r,const VariableValues&v,double t=1e-6)const{return evaluate(r,v)<=t;}protected:static double upper(double a,double b){return std::isfinite(a)?std::max(0.0,a-b):std::numeric_limits<double>::infinity();}static double lower(double a,double b){return std::isfinite(a)?std::max(0.0,b-a):std::numeric_limits<double>::infinity();}std::string name_;};
using ConstraintPtr=std::shared_ptr<Constraint>;
class ResponseTimeConstraint final:public Constraint{public:ResponseTimeConstraint(std::string s,std::string c,double m,std::string n=""):Constraint(std::move(n)),s_(std::move(s)),c_(std::move(c)),m_(m){}double evaluate(const EvaluationResult&r,const VariableValues&)const override{return upper(r.response_time(s_,c_),m_);}std::string generated_name()const override{return "RT_"+s_+(c_.empty()?"":"_"+c_)+"_le_"+std::to_string(m_);}private:std::string s_,c_;double m_;};
class SystemResponseTimeConstraint final:public Constraint{public:SystemResponseTimeConstraint(std::string c,double m,std::string n=""):Constraint(std::move(n)),c_(std::move(c)),m_(m){}double evaluate(const EvaluationResult&r,const VariableValues&)const override{return upper(r.system_response_time(c_),m_);}std::string generated_name()const override{return "SysRT_"+c_+"_le_"+std::to_string(m_);}private:std::string c_;double m_;};
class ThroughputConstraint final:public Constraint{public:ThroughputConstraint(std::string s,std::string c,double m,std::string n=""):Constraint(std::move(n)),s_(std::move(s)),c_(std::move(c)),m_(m){}double evaluate(const EvaluationResult&r,const VariableValues&)const override{return lower(r.throughput(s_,c_),m_);}std::string generated_name()const override{return "Tput_"+s_+(c_.empty()?"":"_"+c_)+"_ge_"+std::to_string(m_);}private:std::string s_,c_;double m_;};
class UtilizationConstraint final:public Constraint{public:UtilizationConstraint(std::string s,double m,std::string n=""):Constraint(std::move(n)),s_(std::move(s)),m_(m){}double evaluate(const EvaluationResult&r,const VariableValues&)const override{return upper(r.utilization(s_),m_);}std::string generated_name()const override{return "Util_"+s_+"_le_"+std::to_string(m_);}private:std::string s_;double m_;};
class BudgetConstraint final:public Constraint{public:BudgetConstraint(double b,std::map<std::string,double>c={},std::string n=""):Constraint(std::move(n)),budget_(b),cost_(std::move(c)){}double cost(const VariableValues&v)const{double x=0;for(const auto&kv:cost_){auto i=v.find(kv.first);if(i!=v.end())x+=kv.second*std::accumulate(i->second.begin(),i->second.end(),0.0);}return x;}double evaluate(const EvaluationResult&,const VariableValues&v)const override{return std::max(0.0,cost(v)-budget_);}std::string generated_name()const override{return "Budget_le_"+std::to_string(budget_);}private:double budget_;std::map<std::string,double>cost_;};
class Objective{public:virtual~Objective()=default;virtual double evaluate(const EvaluationResult&,const VariableValues&)const=0;virtual bool is_minimization()const{return true;}std::vector<ConstraintPtr>constraints;double evaluate_with_penalty(const EvaluationResult&r,const VariableValues&v,double w=1e6)const{double x=evaluate(r,v);for(const auto&c:constraints)x+=c->evaluate(r,v)*w;return x;}}; using ObjectivePtr=std::shared_ptr<Objective>;
class MinimizeCost final:public Objective{public:MinimizeCost(std::map<std::string,double>s={},std::map<std::string,double>r={},std::map<std::string,double>p={},std::vector<ConstraintPtr>c={}):rate_(std::move(r)){for(auto&kv:s)server_[kv.first+"_servers"]=kv.second;for(auto&kv:p)replica_[kv.first+"_replicas"]=kv.second;constraints=std::move(c);}double evaluate(const EvaluationResult&,const VariableValues&v)const override{double x=0;for(const auto&kv:server_){auto i=v.find(kv.first);if(i!=v.end())x+=kv.second*scalar_value(i->second);}for(const auto&kv:replica_){auto i=v.find(kv.first);if(i!=v.end())x+=kv.second*scalar_value(i->second);}for(const auto&rk:rate_)for(const auto&vv:v)if(vv.first.find(rk.first)!=std::string::npos&&vv.first.find("rate")!=std::string::npos)x+=rk.second*scalar_value(vv.second);return x;}private:std::map<std::string,double>server_,rate_,replica_;};
class MinimizeSystemResponseTime final:public Objective{public:explicit MinimizeSystemResponseTime(std::string c="",std::vector<ConstraintPtr>x={}):c_(std::move(c)){constraints=std::move(x);}double evaluate(const EvaluationResult&r,const VariableValues&)const override{return r.system_response_time(c_);}private:std::string c_;};
class MaximizePerformance final:public Objective{public:MaximizePerformance(double tw=1,double rw=1,double qw=0,std::vector<std::string>s={}):tw_(tw),rw_(rw),qw_(qw),stations_(std::move(s)){}double evaluate(const EvaluationResult&r,const VariableValues&)const override{std::vector<std::string>s=stations_;if(s.empty())for(const auto&kv:r.throughputs){auto p=kv.first.find("||");auto n=kv.first.substr(0,p);if(std::find(s.begin(),s.end(),n)==s.end())s.push_back(n);}double x=0;for(const auto&n:s){if(tw_>0)x+=tw_*r.throughput(n);double rt=r.response_time(n);if(rw_>0&&rt>0&&std::isfinite(rt))x+=rw_/rt;double q=r.queue_length(n);if(qw_>0&&q>0)x+=qw_/q;}return -x;}private:double tw_,rw_,qw_;std::vector<std::string>stations_;};
} }
#endif