mac更换office默认语言

2022-09-14

打开终端，输入如下切换至英文

1
2
3

defaults write com.microsoft.Word AppleLanguages '("en")'
defaults write com.microsoft.Excel AppleLanguages '("en")'
defaults write com.microsoft.Powerpoint AppleLanguages '("en")'

若要切回中文.

1
2
3

defaults write com.microsoft.Word AppleLanguages '("zh_CN")'
defaults write com.microsoft.Excel AppleLanguages '("zh_CN")'
defaults write com.microsoft.Powerpoint AppleLanguages '("zh_CN")'

使用mac的shadowsocks共享局域网

2022-09-07

mac的SSR

忘记了是从哪里装的了，好像是开源的。

获取mac本机IP

在mac上获取一下本机的IP，在手机设置的时候需要配置dialing服务器

1	ifconfig\|grep 192

获得192.168.1.3

配置http代理

将IP配置为mac的局域网IP，端口随意，不冲突就好

配置手机代理

先点击wifi名字后面的信息按钮，拉到最下方

选择代理配置，选择手动，配置如下端口即可

分支定界(隐枚举)求解MIP的复现

2022-08-27

分支定界求解MIP的复现

算法思想

分支定界法是本科运筹学课程中学习的求解整数规划的算法之一，分支定界算法的核心思想就是分枝和剪枝。当我们不考虑所求解必须是整数这个条件时，用单纯形法可求出最优解，但是这个解往往不全是整数，因此我们采用剪枝的方式一点一点缩小范围，直到所求解为整数解。

分枝定界法是一种基于“树”结构的搜索或遍历方法
分枝定界法中的整数性判断不会在本质上引起数值困难
定界是为了避免无效的分枝搜索，恰当的分枝有助于更好定界
分枝定界法是部分枚举而不是穷举

算法程序结构和代码

算法由初始化节点，更新上界，更新下界，增加约束获得子问题，求解子问题几部分构成。具体就是在算法主循环中维护一个节点队列和一个等待处理的变量队列，每次循环中出队列一个节点，进行初步计算和判定上下界，并进行减枝，如果顺利计算，则从变量队列中出下一个变量进行分枝，将变量中增加cut后的两个节点push入节点队列，进入下一循环。终止条件是需要分枝计算的变量队列为空。

测试代码和算法class如下。具体使用方式如测试代码所示，输入gurobi.model的建立好的模型和模型中的零一量的namelist即可（后面是用getvarbyname处理的，因此输入的是字符串）。

测试代码



import gurobipy as gp
from gurobipy import GRB
from branch_and_bound_class import *


model = gp.Model("mip1")
x = model.addVars(10, name = 'x', vtype = GRB.BINARY)

model.setObjective(-x[0]  -x[1]  -2*x[2]  -2*x[8] - x[9], GRB.MINIMIZE)
model.addConstr(x[0] + 2*x[1] + 3*x[2] + 5*x[3] + 3*x[4] <= 8, "c0")
model.addConstr(2*x[3] + 2*x[4] + 3*x[5] + 5*x[6] + 3*x[7] <= 10, "c1")
model.addConstr(x[7] + x[8] + 3*x[9] <= 4, "c2")
model.addConstr(2*x[0] + x[2] + 3*x[7] + 3*x[8] + 2*x[9] <= 8, "c3")
model.addConstr(x[7] + x[8] + 3*x[9] >= 1, "c4")
model.addConstr(2*x[4] + 2*x[5] + x[6] + 5*x[7] + 3*x[8] >= 4, "c5")
# model.optimize()


candidate_vars = ['x[0]','x[1]','x[2]','x[3]','x[4]','x[5]','x[6]','x[7]','x[8]','x[9]']




solve(model,candidate_vars)

算法class

import gurobipy as gp
from gurobipy import GRB

"""branch and bound code
输入gurobi的MIP模型 目前仅仅支持binary variable
"""


class Node:
    def __init__(self, model, upper_bound, lower_bound, candidate_vars):
        """初始化节点

        Args:
            model (_type_): gurobi model object
            upper_bound (_type_): _description_
            lower_bound (_type_): _description_
            candidate_vars (_type_): list,NumVars
        """
        self.upper_bound, self.lower_bound = upper_bound, lower_bound
        self.model = model
        # print(candidate_vars,upper_bound,lower_bound)
        self.candidate_vars = candidate_vars.copy()
        assert(upper_bound >= lower_bound), "upper bound is less than lower bound"

    def optimize(self, heuristic_solve):
        """求解Node

        Args:
            heuristic_solve (anotherFuc): 传入函数参数,求解节点的方法

        Returns:
            _type_: _description_
        """
        self.obj_values, self.solution = heuristic_solve(self.model)
        if self.obj_values == None:
            return "infeasible"
        return "feasible"
    
    def update_upper_bound(self):
        """更新upbound,最小化问题的话,上界无条件更新
        """
        # if self.upper_bound > self.obj_values:
        self.upper_bound = self.obj_values
        assert(self.lower_bound <= self.obj_values)
        assert(self.lower_bound <= self.upper_bound), "upper bound is less than lower bound"

    def update_lower_bound(self):
        """更新lowerbound,最小化问题下界条件更新
        """
        if self.lower_bound < self.obj_values:
            self.lower_bound = self.obj_values
            assert(self.lower_bound <= self.obj_values)
            assert(self.lower_bound <= self.upper_bound), "upper bound is less than lower bound"
        
    def is_integer(self):
        """判断解的质量

        Returns:
            _type_: True则表示解OK
        """
        for var in self.solution:
            if 0 < var.x and var.x < 1:
                return False
        return True
    
    def is_child_problem(self):
        # print(self.candidate_vars)
        # print(len(self.candidate_vars))
        if len(self.candidate_vars) > 0:
            return True
    
    def get_child_problem(self):
        """_summary_得替换成GRBgetvarbyname,因为不是所有变量都是binary

        Returns:
            _type_: _description_
        """
        self.child_left, self.child_right = self.model.copy(), self.model.copy()
        branch_index, self.condidate_child_vars = self.choice_branch(self.candidate_vars)
        # 分枝left bound 和 right bound。
        # print(branch_index)
        # print(self.child_left.getVarByName('x0'))
        # for v in self.child_left.getVars():
        #     print('%s' % (v.VarName,))
        self.child_left.addConstr(self.child_left.getVarByName(branch_index) == 0,"left")
        self.child_right.addConstr(self.child_right.getVarByName(branch_index) == 1,"right")
        self.child_left.write("left.lp")
        self.child_right.write("right.lp")
        node_left = Node(self.child_left, self.upper_bound, self.lower_bound, self.condidate_child_vars)
        node_right = Node(self.child_right, self.upper_bound, self.lower_bound, self.condidate_child_vars)

        return node_left, node_right
    
    def choice_branch(self, candidate_vars):
        """选择分枝的变量,这里可以加一些优化,但是似乎不太好加   现在是从等待分枝的变量中直接pop0

        Args:
            candidate_vars (_type_): 维护一个栈,剩余的需要分枝的binary variables

        Returns:
            _type_: _description_
        """
        self.condidate_child_vars = self.candidate_vars.copy()
        branch_index = self.condidate_child_vars.pop(0)  # 改为name后应该弹出的是str：varName
        return branch_index, self.condidate_child_vars
    
    def write(self):
        self.model.write("model.lp")
    

def heuristic_solve(problem):
    problem.Params.OutputFlag = 0
    problem.optimize()
    if problem.status == GRB.INFEASIBLE:
        return None, None
    # for v in problem.getVars():
    #     print('%s %g' % (v.VarName, v.X))
    # print('Obj: %g' % problem.ObjVal)
    return problem.ObjVal, problem.getVars()

def choice_node(condidate_node):
    """选择下一个计算的节点 现在也是pop0

    Args:
        condidate_node (_type_): 维护的还没计算的节点

    Returns:
        _type_: _description_
    """
    node = condidate_node.pop(0)
    return node, condidate_node


def solve(model,candidate_vars):
    model.update()
    upper_bound, lower_bound = float('inf'), float('-inf')
    model_relax = model.relax()
    root_node = Node(model = model_relax, upper_bound = upper_bound, lower_bound = lower_bound, candidate_vars = candidate_vars)
    candidate_node = [root_node]
    current_optimum = None
    while candidate_node:
        # print(candidate_node)
        node, candidate_node = choice_node(candidate_node)
        if node.upper_bound <= lower_bound:
            print("prune by bound")
            continue
        model_status = node.optimize(heuristic_solve)
        if model_status == 'infeasible':
            print("prune by infeasiblity")
            continue
        node.update_lower_bound()
        if node.lower_bound >= upper_bound:
            print("prune by bound")
            continue
        if node.is_integer():
            # print('yes')
            # exit(0)
            node.update_upper_bound()
            # lower bound 
            if node.upper_bound < upper_bound:
                upper_bound = node.upper_bound
                current_optimum = node.solution
            continue

        if node.is_child_problem():
            child_node1, child_node2 = node.get_child_problem()
            candidate_node.append(child_node1)
            candidate_node.append(child_node2)
    print('lower_bound: ',lower_bound)
    print("upper_bound: ", upper_bound)
    print("optimum:", current_optimum)

青训营笔记｜YARN资源调度

2022-08-20

走进 YARN 资源管理和调度

YARN 概述：从食堂分配座位场景导入，初识调度系统；介绍调度系统发展的背景、解决的问题、目标和范型；Hadoop YARN 的设计思想和整体架构；

首先考虑如下虚拟场景，如何进行调度在保障就餐公平性的前提下让尽可能多的学生都能够在该餐厅就餐、尽可能多的座位被有效使用？

学校为改善学生生活新建了一所美食餐厅，餐厅座位有限且只能堂食；
各个学院需要缴纳一定管理费用后其学生才能在该餐厅用餐，缴纳费用与分配的座位数成正比；
因餐厅物美价廉、环境干净，来该餐厅就餐的人络绎不绝；

一种简易的分配模型参考如下：

学院缴纳费用后获得固定座位数；
学生按照学院组织，学院内的用餐小组按照预定时间排队，每个小组有一个负责人；
餐厅经理（两个备用经理）对所有学院按照分配座位满足率由低到高排序，优先选择靠前学院进行餐位派发；
餐厅经理选择一个学院后，基于餐厅座位情况，以 FIFO 方式选择用餐小组并分配桌号；
用餐小组在餐厅经理助手引导下到特定位置进行就餐，用餐小组负责人安排组内成员就坐；
用餐结束后，用餐小组负责人向餐厅助手说明；

调度系统概述

如今，我们已经由信息科技时代（IT）进化到数据科技时代（DT），数据中蕴藏的海量信息激发我们开发各种计算模型和计算框架进行挖掘，而这些计算模型和计算框架最终都需要落地计算。同时数据计算方式也发生了很大变革，从单机到分布式集群再到大规模数据中心，计算越来越快。对于大型互联网公司而言，为了完成各种对外服务以及对内挖掘等任务，需要的硬件资源数以万计，具有较高的成本。

当用有限资源解决有限资源无法满足的需求时就需要调度。如何充分挖掘硬件资源潜力、灵活进行资源管理与调度以及提高集群整体利用率成为降本增效的关键问题。资源资源管理与调度主要解决资源请求和可用资源的映射(Mapping) 问题，也就是将负载的资源请求与当前计算集群中的可用物理资源通过一定的调度策略进行匹配(Matching)。

调度系统设计的基本问题

资源异质性与工作负载异质性
异质性通常指组成元素构成的多元性和相互之间较大的差异性。资源异质性是从系统所拥有的资源角度来看的，对于大型数据中心来说，其采购往往是分批次的，不同批次的机器硬件配置和计算存储资源都存在较大差异，很难保证采用完全相同的配置，目前主要通过将资源分配单位细粒度划分以及虚拟化技术来解决；工作负载异质性是从系统提交的任务角度来看的，负载类型多样化（流处理、批处理、内存计算、在线服务等），任务偏好多样化和动态化（任务的约束条件、运行过程中资源使用动态变化），资源需求多样化（CPU，内存，GPU，IO等），例如对外服务要保证高可用和快速响应，对于批处理任务要保证快速调度等。
数据局部性
大数据场景下因为数据传输开销要远大于计算逻辑传输开销，因此往往将计算任务推送到数据存储所在地进行，这种设计哲学一般被称为数据局部性问题。在资源管理与调度语境下一般存在3种类型数据局部性：节点局部性，机架局部性和全局局部性。节点局部性完成计算不需要进行数据传输，机架局部性需要在机架之间进行数据传输存在一定开销，其它情况则属于全局局部性需要跨机架进行网络传输进而产生较大的网络传输开销，因此最优的方式是尽可能保证节点局部性。
抢占式与非抢占式调度
在多用户多任务场景下，面对已分配资源，资源管理与调度系统有两种不同类型的调度方式：抢占式调度与非抢占式调度。抢占式调度指的是当系统资源不足或存在资源竞争时高优先级的任务可以抢占低优先级任务的资源；非抢占式调度，每次只允许从空闲资源中分配，空闲资源若不足则须等待其它任务释放资源后才能继续推进，mesos采用非抢占式调度。两种方式各有特点，一般如果强调高优先级任务执行效率的调度策略会采用抢占式调度，强调资源公平分配的调度会采用非抢占式调度。
资源分配粒度
大数据场景下的计算任务往往呈现层级结构，例如：作业级（Job）-任务级（Task）-实例级（Instance），从计算任务视角来看，此时资源调度系统就面临资源分配粒度问题，资源分配粒度主要存在三种方式：（1）群体分配策略（Gang Scheduler），即要么全满足要么全不满足，Flink和MPI任务依赖这种方式；（2）增量满足式分配策略，只要分配部分资源就可以启动运行，MR采用这种方式；（3）资源储备策略，资源达到一定量才能启动作业，在未获得足够资源时作业可以先持有目前已经分配的资源并等待其他作业释放资源，调度系统不断获取新资源并进行储备和积累，直到分配到的资源量达到最低标准后开始运行，在作业启动前已经分配的资源处于闲置状态。
饿死与死锁问题
饿死是由于调度策略不当而导致计算任务长时间无法获得开始执行所需要的最少资源量，例如支持优先级调度时，如果不断出现高优先级任务，那么低优先级任务可能饿死；死锁是由于资源分配不当而导致整个调度系统无法正常执行，例如在资源储备策略下，如果AB两个作业启动作业需要的最小资源为2/3，那么如果两个任务被分配了1/2的资源时，就导致死锁。调度系统出现死锁必然表现为某些作业处于饿死状态，但计算任务饿死的情景并不一定意味着调度系统处于死锁状态。
资源隔离方法
为了减少任务之间的干扰需要进行一定的隔离措施，LXC是一种轻量级的内核虚拟化技术，LXC在资源管理方面依赖于 Linux 内核的 cgroups 子系统，cgroups 子系统是 Linux 内核提供的一个基于进程组的资源管理框架，可以为特定的进程组限定可以使用的资源。其他技术有Intel RDT。

资源管理与调度系统范型

集中式调度系统

产生背景：该调度系统是大规模数据分析和云计算出现的雏形，主要进行大规模的集群管理以提高数据处理能力。
基本原理：中心式调度系统融合了资源管理和任务调度，有一个中心式的 JobTracker 负责进行集群资源的合理分配、任务的统一调度、集群计算节点信息的统计维护、任务执行过程中的状态管理等。

优点：

JobTracker 能够感知集群中所有资源和任务的执行状态，能够进行全局最优的资源分配和调度，避免任务间的干扰，适当进行任务抢占，保证任务计算效率和服务质量；
架构模型简单，只有一个全局的管理者负责进行所有管理。

缺点

JobTracker 作为集群的中心，存在单点瓶颈问题，不能支持大规模集群；
内部实现异常复杂，一个调度器中需要实现所有的功能模块，可扩展性差；
负载变更会导致系统需要进行不断的迭代，这将增加系统的复杂性，不利于后期的维护和扩展；
只支持单类型的任务，MR 类型的批处理任务

两层调度系统

产生背景：为了解决集中式调度系统的扩展性问题，系统实现复杂，可扩展性差，不能支持不同类型任务等缺点。

实现原理：将资源管理和任务调度解耦。集群资源管理器负责维护集群中的资源信息并将资源分配给具体的任务，任务管理器负责申请资源并将申请到的资源根据用户逻辑进行细分和具体的任务调度。

优点：
资源管理器只负责资源分配，任务调度由应用完成，提高了系统的扩展性；
任务调度逻辑由具体的任务完成，能够提供对不同类型任务的支持；
内部实现模块化，利于维护和扩展；
缺点：
任务无法感知全局的资源情况，只能基于request/offer来进行资源获取，无法有效避免异构负载之间的性能干扰问题；
任务调度和资源管理解耦不利于实现多任务间的优先级抢占；
所有任务的资源请求都需要资源管理器进行处理，此外其还需要与节点管理器之间维持通信，导致资源管理器存在单点问题；

Mesos 最先将资源管理和任务调度解耦的 offer-based（基于资源供应）方案，其有一个中心的资源管理器，通过分配策略（DRF）将资源分配给不同的计算框架，每个计算框架依据自身的逻辑、资源偏好等采取增量或者 All-or-Nothing 的方式决定接受还是拒绝分配的资源，计算框架根据分配到的资源进行下一步的资源分配和任务执行。

共享状态调度系统

产生背景：前面的调度器存在一个问题就是计算框架在进行资源申请的时候无法获知到集群的全局资源信息，这就导致无法进行全局最优的调度，共享状态调度器就提供了这个问题的一种解决方式。

基本原理：是一个半分布式的架构，通过共享集群状态为应用提供全局的资源视图，并采用乐观并发机制进行资源申请和释放，来提高系统的并发度。

优点：

支持全局最优调度；
能够一定程度的提高并发度；

缺点：

高并发资源请求下会造成频繁的资源竞争；
不利于资源分配的公平性；
资源全局副本维护模块存在单点瓶颈；

分布式调度系统

产生背景：提高系统吞吐率和并发度

基本原理：分布式调度器之间没有通讯协作，每个分布式调度器根据自己最少的先验知识进行最快的决策，每个调度器单独响应任务，总体的执行计划与资源分配服从统计意义。

优点：提高吞吐量和并发度

缺点：

调度质量得不到保障；
资源非公平分配；
不能支持多租户管理；
不能避免不同任务之间的性能干扰；

果果的博客