## 数学代写|组合优化代写Combinatorial optimization代考|New Facets

statistics-lab™ 为您的留学生涯保驾护航 在代写组合优化Combinatorial optimization方面已经树立了自己的口碑, 保证靠谱, 高质且原创的统计Statistics代写服务。我们的专家在代写组合优化Combinatorial optimization代写方面经验极为丰富，各种代写组合优化Combinatorial optimization相关的作业也就用不着说。

• Statistical Inference 统计推断
• Statistical Computing 统计计算
• (Generalized) Linear Models 广义线性模型
• Statistical Machine Learning 统计机器学习
• Longitudinal Data Analysis 纵向数据分析
• Foundations of Data Science 数据科学基础

Several families of valid inequalities were introduced for the problem, in the following we will give the basic valid inequalities that define facets.
The NLP with two cables types is formulated as follows.
Let $G=(V, E)$ be an undirected graph, a set of $M$ commodities $\left{\left(s_{1}, t_{1}\right), \ldots,\left(s_{|M|}, t_{|M|}\right)\right}$, a commodity $q \in{1, \ldots, M}$ having a demand $d_{q}$.
\begin{aligned} &\min \sum_{u \in E E} l_{u v} \gamma^{1} x_{u E}^{1}+l_{w v} \gamma^{2} x_{u E}^{2} \ &\sum_{v \in V} f_{(u, v)}^{q}-\sum_{v \in V} f_{(v, w)}^{q}=\left{\begin{array}{ll} d_{q}, \text { if } u=s_{q} \ -d_{q}, \text { if } u=t_{q}, \ 0, & \text { otherwise. } \end{array} \quad \text { for all } u \in V, q \in{1, \ldots, M}(17)\right. \end{aligned}
\begin{aligned} &\sum_{q=1}^{M}\left(f_{(u, v)}^{k}+f_{(v, u)}^{k}\right) \leq x_{u v}^{1}+C x_{u v}^{2} \ &x_{e}^{1}, x_{e}^{2} \geq 0, \quad \text { for all } e \in E, \ &f_{(u, v)}^{k}, f_{(v, u)}^{k} \geq 0 \text { for all } u v \in E, k \in K . \end{aligned}
Rounded Cut-Set Inequalities. The rounded cut-set inequalities are obtained by partitioning the node set into two subsets, namely $S$ and $\bar{S}$. Magnanti et al. [14] introduced the following form for the rounded cut-set inequalities:
$$x^{1}(\delta(S))+r x^{2}(\delta(S)) \geq r\left\lceil\frac{D_{S, \bar{S}}}{C}\right\rceil$$

where $D_{S, \bar{S}}$ is the total demand whose origin lays in $S$ and destination in $\bar{S}$ and vice-versa, and
$$r=\left{\begin{array}{l} C, \text { if } \quad D_{S, \bar{S}} \quad(\bmod C)=0 \ D_{S, \bar{S}} \quad(\bmod C), \text { otherwise. } \end{array}\right.$$
Theorem 3 [14]. A rounded cut set inequality defines a facet for the $N L P$ if and only if

1. the subgraphs induced by $S$ and by $\bar{S}$ are connected,
2. $D_{S, \bar{S}}>0$.
Partition Inequalities. Several version of partition inequalities have been developed in the literature, in particular, Magnanti et al. [14] gave a family of three-partition inequalities of the following form:
$$x_{12}^{1}+x_{13}^{1}+x_{23}^{1}+r\left(x_{12}^{2}+x_{13}^{2}+x_{23}^{2}\right) \geq\left\lceil\left[\frac{r\left(\left\lceil\frac{d_{12}+d_{13}}{C}\right\rceil+\left\lceil\frac{d_{12}+d_{23}}{C}\right\rceil+\left\lceil\frac{d_{13}+d_{23}}{C}\right\rceil\right)}{2}\right\rceil\right.$$
The following metric inequalities are valid for NLP with one cable type:
Metric Inequalities. Metric inequalities can be introduced after projecting out the flow variables from the polyhedron and obtain a “capacity formulation” in the space of capacity variables. In particular Avella et al. [2] gave a family of metric inequalities that completely describe the polyhedron, they take the form
$$\mu x \geq \rho(\mu, G, d), \mu \in \operatorname{Met}(G)$$
In the next section we present a lifting procedure that extends the Rounded cut-set inequalities defined for NLP to be valid for BBFLP.

## 数学代写|组合优化代写Combinatorial optimization代考|Lifted Rounded Cut-Set Inequalities

Now, we give the main result of the paper which is a new family of valid inequalities for the BBFLP. These latter inequalities are obtained by lifting the rounded cut-set inequalities.

Consider the situation where all the facilities are opened and all the clients are assigned to a facility. For every $j \in D$, let $h_{j}$ be the facility to which it is assigned (Fig. 1).
Let $Q_{0}=\left{(x, y, t) \in Q\right.$ such that $t_{j}^{h}=0$, for all $\left.h \in H \backslash h_{j}, j \in D\right}$.
Lemma 1. The solutions of $Q_{0}$ are exactly solutions of a NLP where the demand set is composed of the pairs $\left(j, h_{j}\right)$, with $j$ the origin, $h_{j}$ the destination and $d_{j}$ is the commodity.

By Lemma 1, every valid inequality (respectively facet defining) for the corresponding NLP polyhedron are valid for $Q_{0}$ (respectively facet defining). This means that rounded cut-set inequalities are valid for $Q_{0}$.

Our objective is to extend the rounded cut-set inequalities by a lifting procedure to obtain facet defining inequalities for BBFLP. Let $(x, y, t) \in Q_{0}$ and $S \subseteq V$ be a node set such that $S \cap V \neq \emptyset \neq \bar{S} \cap V$. Let $A$ (resp. $A^{\prime}$ ) be the node subset of $D \cap S$ (resp. $D \cap \bar{S}$ ) which are assigned to a facility of $H \cap \bar{S}$ (resp. $H \cap S$ ). Also, let $B$ (resp. $B^{\prime}$ ) be the node subset of $D \cap S$ (resp. $D \cap \bar{S}$ ) which are assigned to a facility of $H \cap S$ (resp. $H \cap \bar{S}$ ).
The rounded cut-set inequality induced by $S$ is
$$x^{1}(\delta(S))+r x^{2}(\delta(S)) \geq r\left\lceil\frac{d\left(A \cup A^{\prime}\right)}{C}\right\rceil,$$
where $r=d\left(A \cup A^{\prime}\right)(\bmod C)$. Clearly (24) is valid for $Q_{0}$.
For convenience, we let,
\begin{aligned} &A_{1}=\left{j \in A \cup A^{\prime} \text { such that } d_{j} \leq r\right} \ &A_{2}=\left{j \in A \cup A^{\prime} \text { such that } d_{j}>r\right} \ &B_{1}=\left{j \in B \cup B^{\prime} \text { such that } d_{j} \leq C-r\right}, \ &B_{2}=\left{j \in B \cup B^{\prime} \text { such that } d_{j}>C-r\right} . \end{aligned}
Now we give our main result.
Theorem 4. Let $S \subseteq V$ with $S \cap V \neq \emptyset \neq V \cap \bar{S}$. The inequality
$$x^{1}(\delta(S))+r x^{2}(\delta(S))+\sum_{j \in D} \sum_{\left.h \in H \backslash h_{j}\right}} C_{j}^{h} t_{j}^{h} \geq r\left\lceil\frac{d\left(A \cup A^{\prime}\right)}{C}\right\rceil$$
where
$$C_{j}^{h}=\left{\begin{array}{l} d_{j}, \text { for } j \in A_{1} \cap A, h \in H \cap S \text { and for } \in A_{1} \cap A^{\prime}, h \in H \cap \bar{S}, \ r, \text { for } j \in A_{2} \cap A, h \in H \cap S \text { and for } j \in A_{2} \cap A^{\prime}, h \in H \cap \bar{S} \ C-r-d_{j}, \text { for } j \in B_{1} \cap B, h \in H \cap \bar{S} \text { and for } j \in B_{1} \cap B^{\prime}, h \in H \cap S, \ 0, \text { otherwise. } \end{array}\right.$$
is valid for BBFLP. Moreover (25) is facet for $Q$ if (24) is facet for $Q_{0}$.

## 数学代写|组合优化代写Combinatorial optimization代考|A Polyhedral Study for the Buy-at-Bulk Facility Location Problem

Lemma 3. If $D^{\prime}=\emptyset$ then, for every $j_{0} \in A \cup A^{\prime}$ and $h_{0} \in H \backslash\left{h_{j_{0}}\right}$,
$$\xi_{j_{0}}^{h_{0}}=r\left\lceil\frac{d(W)}{C}\right\rceil+\varepsilon_{W}$$
where $W=\left(A \cup A^{\prime}\right) \backslash\left{j_{0}\right}$.
Proof. First, let $\beta$ be the number of cables of type 1 loaded on the edges of $\delta(S)$. Also, w.l.o.g., we assume that the number of cables of type 2 loaded on the edges of $\delta(S)$ is $\left\lceil\frac{d(W)}{C}\right\rceil-\lambda$, for some $\lambda \geq 0$. In any feasible solution of the BBFLP, we have that $\beta+C\left(\left\lceil\frac{d(W)}{C}\right\rceil-\lambda\right) \geq d(W)$.

We have that $x^{1}(\delta(S))+r x^{2}(\delta(S))=\beta+r\left(\left\lceil\frac{d(W)}{C}\right\rceil-\lambda\right)$. If $\lambda=0$, we can show that the minimum value of $x^{1}(\delta(S))+r x^{2}(\delta(S))$ is obtained for $\beta=0$. Thus, $\xi_{j_{0}}^{h_{0}}=r\left\lceil\frac{d(W)}{C}\right\rceil$ in this case. Now, if $\lambda \geq 1$, we have that
$$\beta+r\left(\left\lceil\frac{d(W)}{C}\right\rceil-\lambda\right) \geq(C-r) \lambda-C+r_{W}+r\left\lceil\frac{d(W)}{C}\right\rceil .$$
Here also, we can show that the minimum of $x^{1}(\delta(S))+r x^{2}(\delta(S))$ is obtained for $\lambda=1$ and $\beta=C(\lambda-1)+r_{W}=r_{W}$, that is $\xi_{j_{0}}^{h_{0}}=r_{W}-r+r\left\lceil\frac{d(W)}{C}\right\rceil$.
Thus, $\xi_{j_{0}}^{h_{0}}=r\left\lceil\frac{d(W)}{C}\right\rceil+\min \left{0, r_{W}-r\right}=r\left\lceil\frac{d(W)}{C}\right\rceil+\varepsilon_{W}$.
Lemma 4. If $D^{\prime}=\emptyset$ then, for every $j_{0} \in B \cup B^{\prime}$ and $h_{0} \in H \backslash\left{h_{j_{0}}\right}$,
$$\xi_{j_{0}}^{h_{0}}=r\left\lceil\left[\frac{d(W)}{C}\right\rceil+\varepsilon_{W}\right.$$
where $W=A \cup A^{\prime} \cup\left{j_{0}\right}$.
Now, for a node set $U \subseteq D$, we let
$$\alpha_{U}=\left\lceil\frac{d\left(A \cup A^{\prime}\right)}{C}\right\rceil-\left\lceil\frac{d(U)}{C}\right\rceil .$$
From Lemmas 3 and 4 , when $D^{\prime}=\emptyset$, the lifting coefficient of a variable $t_{j_{0}}^{h_{0}}$ is of the form
$$C_{j_{0}}^{h_{0}}=r \alpha_{W}-\varepsilon_{W}$$
where
$$W=\left{\begin{array}{l} \left(A \cup A^{\prime}\right) \backslash\left{j_{0}\right}, \text { for } j_{0} \in A \cup A^{\prime}, \ A \cup A^{\prime} \cup\left{j_{0}\right}, \text { for } j_{0} \in B \cup B^{\prime} . \end{array}\right.$$
From this, we can see that the lifting coefficient of variable $t_{j}^{h}$, when $D^{\prime}=\emptyset$ ({i.e. $}$ when the variable is lifted at first), is
$-C_{j}^{h}=r \alpha_{W}-\varepsilon_{W}=d_{j}$, for $j \in A_{1}$,
$-C_{j}^{h}=r \alpha_{W}-\varepsilon_{W}=r$, for $j \in A_{2}$,
$-C_{j}^{h}=r \alpha_{W}-\varepsilon_{W}=0$, for $j \in B_{1}$,
$-C_{j}^{h}=r \alpha_{W}-\varepsilon_{W}=C-r-d_{j}$, for $j \in B_{2} .$

## 组合优化代写

\begin{aligned} &\min \sum_{u \in EE} l_{uv} \gamma^{1} x_{u E}^{1}+l_{wv} \gamma^{2} x_{ u E}^{2} \ &\sum_{v \in V} f_{(u, v)}^{q}-\sum_{v \in V} f_{(v, w)}^{q} =\左{dq, if u=sq −dq, if u=tq, 0, otherwise. \quad \text { for all } u \in V, q \in{1, \ldots, M}(17)\right. \end{对齐} ∑q=1M(f(u,v)k+f(v,u)k)≤xuv1+Cxuv2 xe1,xe2≥0, for all e∈E, f(u,v)k,f(v,u)k≥0 for all uv∈E,k∈K. RoundedCut−SetInequalities.Theroundedcut−setinequalitiesareobtainedbypartitioningthenodesetintotwosubsets,namelySandS¯.Magnantietal.[14]introducedthefollowingformfortheroundedcut−setinequalities: x^{1}(\delta(S))+rx^{2}(\delta(S)) \geq r\left\lceil\frac{D_{S, \bar{S}}}{C}\对\rceil

$$r=\left{C, if DS,S¯(modC)=0 DS,S¯(modC), otherwise. \对。$$

1. 子图由S并通过S¯连接，
2. DS,S¯>0.
分区不等式。文献中已经发展了几个版本的分区不等式，特别是 Magnanti 等人。[14] 给出了以下形式的三分区不等式族：
x121+x131+x231+r(x122+x132+x232)≥⌈[r(⌈d12+d13C⌉+⌈d12+d23C⌉+⌈d13+d23C⌉)2⌉
以下度量不等式对具有一种电缆类型的 NLP 有效：
度量不等式。将多面体中的流量变量投影出来后，可以引入度量不等式，得到容量变量空间中的“容量公式”。特别是 Avella 等人。[2] 给出了一系列完全描述多面体的度量不等式，它们采用以下形式
μx≥ρ(μ,G,d),μ∈Met⁡(G)
在下一节中，我们将介绍一个提升程序，它将为 NLP 定义的圆角割集不等式扩展为对 BBFLP 有效。

## 数学代写|组合优化代写Combinatorial optimization代考|Lifted Rounded Cut-Set Inequalities

x1(δ(S))+rx2(δ(S))≥r⌈d(A∪A′)C⌉,

\begin{对齐} &A_{1}=\left{j \in A \cup A^{\prime} \text { 这样 } d_{j} \leq r\right} \ &A_{2}=\left{ j \in A \cup A^{\prime} \text { 这样 } d_{j}>r\right} \ &B_{1}=\left{j \in B \cup B^{\prime} \text { 这样 } d_{j} \leq Cr\right}, \ &B_{2}=\left{j \in B \cup B^{\prime} \text { 这样 } d_{j}>Cr\right } 。\end{对齐}\begin{aligned} &A_{1}=\left{j \in A \cup A^{\prime} \text { such that } d_{j} \leq r\right} \ &A_{2}=\left{j \in A \cup A^{\prime} \text { such that } d_{j}>r\right} \ &B_{1}=\left{j \in B \cup B^{\prime} \text { such that } d_{j} \leq C-r\right}, \ &B_{2}=\left{j \in B \cup B^{\prime} \text { such that } d_{j}>C-r\right} . \end{aligned}

x^{1}(\delta(S))+r x^{2}(\delta(S))+\sum_{j \in D} \sum_{\left.h \in H \反斜杠 h_{j} \right}} C_{j}^{h} t_{j}^{h} \geq r\left\lceil\frac{d\left(A \cup A^{\prime}\right)}{C} \对\rceilx^{1}(\delta(S))+r x^{2}(\delta(S))+\sum_{j \in D} \sum_{\left.h \in H \backslash h_{j}\right}} C_{j}^{h} t_{j}^{h} \geq r\left\lceil\frac{d\left(A \cup A^{\prime}\right)}{C}\right\rceil

$$C_{j}^{h}=\left{dj, for j∈A1∩A,h∈H∩S and for ∈A1∩A′,h∈H∩S¯, r, for j∈A2∩A,h∈H∩S and for j∈A2∩A′,h∈H∩S¯ C−r−dj, for j∈B1∩B,h∈H∩S¯ and for j∈B1∩B′,h∈H∩S, 0, otherwise. \对。$$

## 数学代写|组合优化代写Combinatorial optimization代考|A Polyhedral Study for the Buy-at-Bulk Facility Location Problem

ξj0h0=r⌈d(W)C⌉+εW

β+r(⌈d(W)C⌉−λ)≥(C−r)λ−C+rW+r⌈d(W)C⌉.

ξj0h0=r⌈[d(W)C⌉+εW

αU=⌈d(A∪A′)C⌉−⌈d(U)C⌉.

Cj0h0=rαW−εW

$$W=\left{\begin{array}{l} \left(A \cup A^{\prime}\right) \backslash\left{j_{0}\right}, \text { for } j_{0} \in A \cup A^{\prime}, \ A \cup A^{\prime} \cup\left{j_{0}\right}, \text { for } j_{0} \in B \cup B^{\prime} . \结束{数组}\begin{array}{l} \left(A \cup A^{\prime}\right) \backslash\left{j_{0}\right}, \text { for } j_{0} \in A \cup A^{\prime}, \ A \cup A^{\prime} \cup\left{j_{0}\right}, \text { for } j_{0} \in B \cup B^{\prime} . \end{array}\对。$$

−Cjh=rαW−εW=dj， 为了j∈A1,
−Cjh=rαW−εW=r， 为了j∈A2,
−Cjh=rαW−εW=0， 为了j∈B1,
−Cjh=rαW−εW=C−r−dj， 为了j∈B2.

## 有限元方法代写

tatistics-lab作为专业的留学生服务机构，多年来已为美国、英国、加拿大、澳洲等留学热门地的学生提供专业的学术服务，包括但不限于Essay代写，Assignment代写，Dissertation代写，Report代写，小组作业代写，Proposal代写，Paper代写，Presentation代写，计算机作业代写，论文修改和润色，网课代做，exam代考等等。写作范围涵盖高中，本科，研究生等海外留学全阶段，辐射金融，经济学，会计学，审计学，管理学等全球99%专业科目。写作团队既有专业英语母语作者，也有海外名校硕博留学生，每位写作老师都拥有过硬的语言能力，专业的学科背景和学术写作经验。我们承诺100%原创，100%专业，100%准时，100%满意。

## MATLAB代写

MATLAB 是一种用于技术计算的高性能语言。它将计算、可视化和编程集成在一个易于使用的环境中，其中问题和解决方案以熟悉的数学符号表示。典型用途包括：数学和计算算法开发建模、仿真和原型制作数据分析、探索和可视化科学和工程图形应用程序开发，包括图形用户界面构建MATLAB 是一个交互式系统，其基本数据元素是一个不需要维度的数组。这使您可以解决许多技术计算问题，尤其是那些具有矩阵和向量公式的问题，而只需用 C 或 Fortran 等标量非交互式语言编写程序所需的时间的一小部分。MATLAB 名称代表矩阵实验室。MATLAB 最初的编写目的是提供对由 LINPACK 和 EISPACK 项目开发的矩阵软件的轻松访问，这两个项目共同代表了矩阵计算软件的最新技术。MATLAB 经过多年的发展，得到了许多用户的投入。在大学环境中，它是数学、工程和科学入门和高级课程的标准教学工具。在工业领域，MATLAB 是高效研究、开发和分析的首选工具。MATLAB 具有一系列称为工具箱的特定于应用程序的解决方案。对于大多数 MATLAB 用户来说非常重要，工具箱允许您学习应用专业技术。工具箱是 MATLAB 函数（M 文件）的综合集合，可扩展 MATLAB 环境以解决特定类别的问题。可用工具箱的领域包括信号处理、控制系统、神经网络、模糊逻辑、小波、仿真等。

## 数学代写|组合优化代写Combinatorial optimization代考|A Polyhedral Study for the Buy-at-Bulk Facility Location Problem

statistics-lab™ 为您的留学生涯保驾护航 在代写组合优化Combinatorial optimization方面已经树立了自己的口碑, 保证靠谱, 高质且原创的统计Statistics代写服务。我们的专家在代写组合优化Combinatorial optimization代写方面经验极为丰富，各种代写组合优化Combinatorial optimization相关的作业也就用不着说。

• Statistical Inference 统计推断
• Statistical Computing 统计计算
• (Generalized) Linear Models 广义线性模型
• Statistical Machine Learning 统计机器学习
• Longitudinal Data Analysis 纵向数据分析
• Foundations of Data Science 数据科学基础

## 数学代写|组合优化代写Combinatorial optimization代考|Introduction

The Buy-at-Bulk facility location problem (BBFLP for short) is defined by an undirected graph $G=(V, E)$, where $V$ denotes the set of nodes and $E$ denotes the set of edges. We are given a set of clients $D \subseteq V$ and a set of facilities $H \subseteq V$. Each client $j \in D$ has a positive demand $d_{j}$. Each facility $h \in H$ is associated with an opening cost $\mu_{h}$. We also have a set $K$ of different cable types. Each cable type $k \in K$ has a capacity $u_{k}$ and a set-up cost per unit length denoted by $\gamma_{k}$. Finally, for each edge $e \in E$ we consider a length $l_{e} \in \mathbb{Z}^{+}$. We assume that the cable types satisfy the so-called economies of scales in that if we let $K={1, \ldots,|K|}$ such that $u_{1} \leq u_{2} \leq \ldots \leq u_{K}, \gamma_{1} \leq \gamma_{2} \leq \ldots \leq \gamma_{K}$, and $\gamma_{1} / u_{1} \geq \gamma_{2} / u_{2} \geq \ldots \geq \gamma_{K} / u_{K}$. A solution of the BBFLP consists in choosing

• a set of facilities to open.
• an assignment of each client to exactly one opened facility,
• a number of cables of each type to be installed on each edge of the graph in order to route the demands from each client to the facility to which it is assigned.

The BBFLP is closely related to the facility location problem and network loading problem. It has many applications in telecommunications and transportation network design. It is not hard to see that the BBFLP contains the Facility Location problem and hence it is NP-hard.

In the literature, the BBFLP was mainly studied in the perspective of approximation algorithms. It was first studied by Meyrson et al. [17] who considered a cost-distance problem and present the BBFLP as a special case of this latter problem. In their work, they provided an $O(\log |D|)$ approximation algorithm.
Ravi et al. [19] gave an $O(k)$ approximation algorithm for the BBFLP where $k$ is the number of cable types. Later, Friggst et al. [13] considered an integer programming formulation for the BBFLP, and showed that this formulation has an integrality gap of $O(k)$. They also considered the variant of the BBFLP where the opened facilities must be connected and gave an integrality gap of $O(1)$. Recently, Bley et al. [7] presented the first exact algorithm for the problem. They introduced a path-based formulation for the problem and compare it with a compact flow-based formulation. They also design an exact branch-and-priceand-cut algorithm for solving the path-based formulation.

As mentioned before, the BBFLP is related to the Network Loading Problem (NLP) and the Facility Location Problem (FLP). Both problems have received a lot of attention. Concerning, the NLP, Magnanti et al. [14] studied the NLP from a polyhedral point of view. They introduced some classes of valid inequalities and devised a Branch-and-Cut algorithm. In [15], Magnanti et al. considered the NLP with two cable types and some particular graphs and gave a complete description of the associated polyhedron in these cases. Bienstock et al. [6] studied the NLP with two cable types with possible extension to more than three cable types. Barahona [9] addressed the same problem, he used a relaxation without flow variables, this relaxation is based on cut condition for multicommodity flows. Gülnük [11] gave a branch and cut algorithm using spanning tree inequalities and mixed integer rounding inequalities. Agarwal [3] has introduced 4-partition based facets. Agarwal [4] extended his previous work and get a complete description of the 4-node network design problem. Raacker et al. [18] have extended the polyhedral results for cut-based inequalities for network design problem with directed, bidirected and undirected link-capacity models. Agarwal [5] developed the total-capacity inequalities, one-two inequalities and spanning trees inequalities based on a p-partition of the graph and discuss conditions under which these inequalities are facet-defining.

## 数学代写|组合优化代写Combinatorial optimization代考|Integer Programming Formulation and Polyhedron

Now, we give the so-called cut formulation for the BBFLP. This formulation can be obtained by slightly modifying the flow-based formulation introduced by [7] and projecting out the flow variables. The cut formulation is given below. Variable $t_{j}^{h}$ equals 1 if the client $j$ is assigned to facility $h$, for all $j \in D$ and $h \in H$, and $x_{e}^{k}$ is the number of cable of type $k$ installed on edge $e$, for all $e \in E$ and $k \in K$.
$\min \sum_{h \in H} \mu_{h} y_{h}+\sum_{e \in E} \sum_{k \in K} \gamma^{k} l_{e}^{k} x_{e}^{k}$
$\sum_{h \in H} t_{j}^{h}=1$,
for all $j \in D$
$t_{j}^{h} \leq y_{h}$,
for all $h \in H, j \in D$
$h \in H, j \in D$
$\sum_{\varepsilon \in \delta(W)} \sum_{k \in K} u_{k} x_{e}^{k} \geq \sum_{j \in W \cap D_{h}} \sum_{h \cap H \bar{S}} t_{j}^{h} d_{j}+\sum_{j \in W \cap D} \sum_{h \in H \cap S} t_{j}^{h} d_{j}$, for all $W \subseteq D$,
$S \subseteq V, \bar{S} \subseteq V \backslash S \quad$ (3)
$t_{j}^{h} \geq 0, \quad$ for all $h \in H, j \in D$, (4)
$y_{h} \leq 1, \quad$ for all $h \in H$,
$x_{e}^{k} \geq 0, \quad$ for all $k \in K, e \in E$, (6)
$t_{j}^{h} \in{0,1}, \quad$ for all $h \in H, j \in D$, (7)
$y_{h} \in{0,1}, \quad$ for all $h \in H$,
$x_{e}^{k} \in \mathbb{Z}^{+}, \quad$ for all $k \in K, e \in E$.
The constraints (1) impose that each client must be assigned to exactly one facility. Constraints (2) are the linking constraints and state that the clients can not be assigned to not open facilities. Constraints (3) are the so-called cut-set inequalities ensuring that the capacity on the edges of the graph is enough for routing all the demands. Constraints (4), (5) and (6) are trivial constraints. Constraints ( 7$),(8)$ and $(9)$ are the integrality constraints.
In the remain of this paper we focus on the cut formulation.
Let $Q=\left{(x, y, t) \in \mathbb{R}^{|E||K|} \times \mathbb{R}^{|H|} \times \mathbb{R}^{|H||D|}\right.$ such that $(x, y, t)$ satisfying (1)-(9) $}$. In the following, we give the dimension of the polyhedron and show that all the trivial inequalities define facets.

## 数学代写|组合优化代写Combinatorial optimization代考|Facets from Facility Location Problem

One can easily see that the projection of $Q$ on variables $y$ and $t$ corresponds to the solutions of a FLP. Thus every valid inequality (resp. facet) for the FLP polytope, in the space of $y$ and $t$ variables is also valid (resp. facet) for $Q$. Let $l_{j h}$ be the cost of assigning client $j$ to facility $h$, recall that the FLP is formulated as follows.
$$\begin{gathered} \min \sum_{j \in D} \sum_{h \in H} l_{j h} t_{j}^{h}+\sum_{h \in H} \mu_{h} y_{h} \ \sum_{h \in H} t_{j}^{h}=1, \quad j \in D \ t_{j}^{h} \leq y_{h}, \quad h \in H, j \in D \ t_{j}^{h} \in{0,1}, \quad h \in H, j \in D \ y_{i} \in{0,1} \quad h \in H . \end{gathered}$$
In what follows, we give some valid inequalities for the FLP which, from the above remarks, are also valid for the BBFLP. Note that under some conditions, these inequalities define facets of $Q$. For more details on valid inequalities and facets associated with FLP, the reader can refer to [10]. In particularly, the following inequalities are valid for facility location problem.

Circulant and Odd Cycle Inequalities. Cornuejols et al. [8] introduced the following. Let $p, q$ be integers satisfying $2 \leq q<p \leq m$ and $p \leq n, p$ is not multiple of $q, s_{1}, \ldots, s_{p}$ be distinct facilities, $m_{1}, \ldots, m_{p}$ be distinct clients, all the indices are modulo $p$ the following inequality is valid for facility location problem.
$$\sum_{i=1}^{p} \sum_{j=i}^{i+q-1} t\left(s_{i}, m_{j}\right) \leq \sum_{h=1}^{p} y\left(s_{i}\right)+p-\lceil p / q\rceil$$
Where $t\left(s_{i}, m_{j}\right)=\sum_{i \in s_{i}} \sum_{i \in m_{j}} t_{j}^{i}, y(S s i)=\sum_{i \in s_{i}} y_{i}$, they called the inequality above circulant inequality. Guignard [12] showed that this inequality defines facet when $p=q+1$, and it is called simple, and when $q=2$ it is called odd cycle inequality.

(p,q) Inequalities. Ardal et al. [1] addressed a family of valid inequalities $(p, q)$ inequalities. Let $p, q$ be integers, $2 \leq q \leq p \leq n, p$ is not multiple of $q, H^{\prime} \subseteq H$, $\left|H^{\prime}\right| \geq\lceil p / q\rceil, D^{\prime} \subseteq D,\left|D^{\prime}\right|=p, \tilde{G}$ is a bipartie graph having $H^{\prime}$ and $J^{\prime}$ as a node set, and $\forall h \in H^{\prime}$ degree(h) $=q$, and the set of edges of $G$ is $\tilde{E}$. The $(p, q)$ inequalities are defined as follows.
$$\text { where } t(\tilde{E})=\sum_{{i, j} \in E} t_{j}^{h} .$$

## 数学代写|组合优化代写Combinatorial optimization代考|Introduction

Buy-at-Bulk 设施选址问题（简称 BBFLP）由无向图定义G=(在,和)， 在哪里在表示节点集和和表示边的集合。我们有一组客户D⊆在和一套设施H⊆在. 每个客户j∈D有积极的需求dj. 各设施H∈H与开盘成本相关μH. 我们还有一套ķ不同的电缆类型。每种电缆类型ķ∈ķ有能力在ķ每单位长度的设置成本表示为Cķ. 最后，对于每条边和∈和我们考虑一个长度l和∈从+. 我们假设电缆类型满足所谓的规模经济，如果我们让ķ=1,…,|ķ|这样在1≤在2≤…≤在ķ,C1≤C2≤…≤Cķ， 和C1/在1≥C2/在2≥…≥Cķ/在ķ. BBFLP 的解决方案在于选择

• 一套设施开放。
• 将每个客户分配到一个完全开放的设施，
• 将在图表的每条边上安装许多每种类型的电缆，以便将每个客户的需求路由到分配给它的设施。

BBFLP 与设施位置问题和网络负载问题密切相关。它在电信和交通网络设计中有许多应用。不难看出 BBFLP 包含设施位置问题，因此它是 NP 难的。

## 数学代写|组合优化代写Combinatorial optimization代考|Integer Programming Formulation and Polyhedron

∑H∈H吨jH=1,

H∈H,j∈D
∑e∈d(在)∑ķ∈ķ在ķX和ķ≥∑j∈在∩DH∑H∩H小号¯吨jHdj+∑j∈在∩D∑H∈H∩小号吨jHdj， 对全部在⊆D,

X和ķ≥0,对全部ķ∈ķ,和∈和, (6)

X和ķ∈从+,对全部ķ∈ķ,和∈和.

## 数学代写|组合优化代写Combinatorial optimization代考|Facets from Facility Location Problem

∑一世=1p∑j=一世一世+q−1吨(s一世,米j)≤∑H=1p是(s一世)+p−⌈p/q⌉

(p,q) 不等式。阿达尔等人。[1] 解决了一系列有效的不等式(p,q)不平等。让p,q为整数，2≤q≤p≤n,p不是的倍数q,H′⊆H, |H′|≥⌈p/q⌉,D′⊆D,|D′|=p,G~是一个具有H′和Ĵ′作为一个节点集，并且∀H∈H′学位（h）=q, 和边的集合G是和~. 这(p,q)不等式定义如下。
在哪里 吨(和~)=∑一世,j∈和吨jH.

## 有限元方法代写

tatistics-lab作为专业的留学生服务机构，多年来已为美国、英国、加拿大、澳洲等留学热门地的学生提供专业的学术服务，包括但不限于Essay代写，Assignment代写，Dissertation代写，Report代写，小组作业代写，Proposal代写，Paper代写，Presentation代写，计算机作业代写，论文修改和润色，网课代做，exam代考等等。写作范围涵盖高中，本科，研究生等海外留学全阶段，辐射金融，经济学，会计学，审计学，管理学等全球99%专业科目。写作团队既有专业英语母语作者，也有海外名校硕博留学生，每位写作老师都拥有过硬的语言能力，专业的学科背景和学术写作经验。我们承诺100%原创，100%专业，100%准时，100%满意。

## MATLAB代写

MATLAB 是一种用于技术计算的高性能语言。它将计算、可视化和编程集成在一个易于使用的环境中，其中问题和解决方案以熟悉的数学符号表示。典型用途包括：数学和计算算法开发建模、仿真和原型制作数据分析、探索和可视化科学和工程图形应用程序开发，包括图形用户界面构建MATLAB 是一个交互式系统，其基本数据元素是一个不需要维度的数组。这使您可以解决许多技术计算问题，尤其是那些具有矩阵和向量公式的问题，而只需用 C 或 Fortran 等标量非交互式语言编写程序所需的时间的一小部分。MATLAB 名称代表矩阵实验室。MATLAB 最初的编写目的是提供对由 LINPACK 和 EISPACK 项目开发的矩阵软件的轻松访问，这两个项目共同代表了矩阵计算软件的最新技术。MATLAB 经过多年的发展，得到了许多用户的投入。在大学环境中，它是数学、工程和科学入门和高级课程的标准教学工具。在工业领域，MATLAB 是高效研究、开发和分析的首选工具。MATLAB 具有一系列称为工具箱的特定于应用程序的解决方案。对于大多数 MATLAB 用户来说非常重要，工具箱允许您学习应用专业技术。工具箱是 MATLAB 函数（M 文件）的综合集合，可扩展 MATLAB 环境以解决特定类别的问题。可用工具箱的领域包括信号处理、控制系统、神经网络、模糊逻辑、小波、仿真等。

## 数学代写|组合优化代写Combinatorial optimization代考|k-edge-connected Spanning Subgraph Polyhedron

statistics-lab™ 为您的留学生涯保驾护航 在代写组合优化Combinatorial optimization方面已经树立了自己的口碑, 保证靠谱, 高质且原创的统计Statistics代写服务。我们的专家在代写组合优化Combinatorial optimization代写方面经验极为丰富，各种代写组合优化Combinatorial optimization相关的作业也就用不着说。

• Statistical Inference 统计推断
• Statistical Computing 统计计算
• (Generalized) Linear Models 广义线性模型
• Statistical Machine Learning 统计机器学习
• Longitudinal Data Analysis 纵向数据分析
• Foundations of Data Science 数据科学基础

## 数学代写|组合优化代写Combinatorial optimization代考|k-edge-connected Spanning Subgraph Polyhedron

The dominant of a polyhedron $P$ is $\operatorname{dom}(P)={x: x=y+z$, for $y \in P$ and $z \geq \mathbf{0}}$. Note that $P_{k}(G)$ is the dominant of the convex hull of all $k$-edgeconnected spanning subgraphs of $G$ that have each edge taken at most $k$ times. Since the dominant of a polyhedron is a polyhedron, $P_{k}(G)$ is a polyhedron even though it is the convex hull of an infinite number of points.

From now on, $k \geq 2$. Didi Biha and Mahjoub (1996) gave a complete description of $P_{k}(G)$ for all $k$, when $G$ is series-parallel.

Theorem 2. Let $G$ be a series-parallel graph and $k$ be a positive integer. Then, when $k$ is even, $P_{k}(G)$ is described by:
(1) $\left{\begin{array}{l}x(D) \geq k \text { for all cuts } D \text { of } G, \ x \geq 0\end{array}\right.$
and when $k$ is odd, $P_{k}(G)$ is described by:
(2) $\left{\begin{array}{l}x(M) \geq \frac{k+1}{2} d_{M}-1 \text { for all multicuts } M \text { of } G, \ x \geq 0 .\end{array}\right.$
The incidence vector of a family $F$ of $E$ is the vector $\chi^{F}$ of $\mathbb{Z}^{E}$ such that $e$ ‘s coordinate is the multiplicity of $e$ in $F$ for all $e$ in $E$. Since there is a bijection between families and their incidence vectors, we will often use the same terminology for both. Since the incidence vector of a multicut $\delta\left(V_{1}, \ldots, V_{d_{M}}\right)$ is the half-sum of the incidence vectors of the bonds $\delta\left(V_{1}\right), \ldots, \delta\left(V_{d_{M}}\right)$, we can deduce an alternative description of $P_{2 h}(G)$.

Corollary 1. Let $G$ be a series-parallel graph and $k$ be a positive even integer. Then $P_{k}(G)$ is described by:
$$\left{\begin{array}{l} x(M) \geq \frac{k}{2} d_{M} \text { for all multicuts } M \text { of } G, \ x \geq \mathbf{0} . \end{array}\right.$$
We call constraints (2a) and (3a) partition constraints. A multicut $M$ is tight for a point of $P_{k}(G)$ if this point satisfies with equality the partition constraint (2a) (resp. (3a)) associated with $M$ when $k$ is odd (resp. even). Moreover, $M$ is tight for a face $F$ of $P_{k}(G)$ if it is tight for all the points of $F$.

The following results give some insight on the structure of tight multicuts.
Theorem 3 (Didi Biha and Mahjoub (1996)). Let $k>1$ be odd, let $x$ be a point of $P_{k}(G)$, and let $M=\delta\left(V_{1}, \ldots, V_{d_{M}}\right)$ be a multicut tight for $x$. Then, the following hold:
(i) if $d_{M} \geq 3$, then $x\left(\delta\left(V_{i}\right) \cap \delta\left(V_{j}\right)\right) \leq \frac{k+1}{2}$ for all $i \neq j \in\left{1, \ldots, d_{M}\right}$.
(ii) $G \backslash V_{i}$ is connected for all $i=1, \ldots, d_{M}$.
Observation 4. Let $M$ be a multicut of $G$ strictly containing $\delta(v)={f, g}$. If $M$ is tight for a point of $P_{k}(G)$, then both $M \backslash f$ and $M \backslash g$ are multicuts of $G$ of order $d_{M}-1$.

Chopra (1994) gave sufficient conditions for an inequality to be facet defining. The following proposition is a direct consequence of (Chopra 1994, Theorem 2.4).

## 数学代写|组合优化代写Combinatorial optimization代考|Box-TDIness of Pk

In this section we show that, for $k \geq 2, P_{k}(G)$ is a box-TDI polyhedron if and only if $G$ is series-parallel.

When $k \geq 2, P_{k}(G)$ is not box-TDI for all graphs as stated by the following lemma.

Lemma 1. For $k \geq 2$, if $G=(V, E)$ contains a $K_{4}$-minor, then $P_{k}(G)$ is not box-TDI.

Proof. When $k$ is odd, Proposition 2 shows that there exists a facet-defining inequality that is described by a non equimodular matrix. Thus, $P_{k}(G)$ is not box-TDI by Statement (ii) of Theorem 1 .

We now prove the case when $k$ is even. Since $G$ is connected and has a $K_{4^{-}}$ minor, there exists a partition $\left{V_{1}, \ldots, V_{4}\right}$ of $V$ such that $G\left[V_{i}\right]$ is connected and $\delta\left(V_{i}, V_{j}\right) \neq \emptyset$ for all $i<j \in{1, \ldots, 4}$. We prove that the matrix $T$ whose three rows are $\chi^{\delta\left(V_{i}\right)}$ for $i=1,2,3$ is a face-defining matrix for $P_{k}(G)$ which is not equimodular. This will end the proof by Statement (ii) of Theorem 1 .

Let $e_{i j}$ be an edge in $\delta\left(V_{i}, V_{j}\right)$ for all $i<j \in{1, \ldots, 4}$. The submatrix of $T$ formed by the columns associated with edges $e_{i j}$ is the following:

The matrix $T$ is not equimodular as the first three columns form a matrix of determinant $-2$ whereas the last three ones have determinant 1 .

To show that $T$ is face-defining, we exhibit $|E|-2$ affinely independent points of $P_{k}(G)$ satisfying the partition constraint (3a) associated with the multicut $\delta\left(V_{i}\right)$, that is, $x\left(\delta\left(V_{i}\right)\right)=k$, for $i=1,2,3$.

Let $D_{1}=\left{e_{12}, e_{14}, e_{23}, e_{34}\right}, D_{2}=\left{e_{12}, e_{13}, e_{24}, e_{34}\right}, D_{3}=\left{e_{13}, e_{14}, e_{23}, e_{24}\right}$ and $D_{4}=\left{e_{14}, e_{24}, e_{34}\right}$. First, we define the points $S_{j}=\sum_{i=1}^{4} k \chi^{E\left[V_{i}\right]}+\frac{k}{2} \chi^{D_{j}}$, for $j=1,2,3$, and $S_{4}=\sum_{i=1}^{4} k \chi^{E\left[V_{i}\right]}+k \chi^{D_{4}}$. Note that they are affinely independent.
Now, for each edge $e \notin\left{e_{12}, e_{13}, e_{14}, e_{23}, e_{24}, e_{34}\right}$, we construct the point $S_{c}$ as follows. When $e \in E\left[V_{i}\right]$ for some $i=1, \ldots, 4$, we define $S_{c}=S_{4}+\chi^{e}$. Adding the point $S_{e}$ maintains affine independence as $S_{e}$ is the only point not satisfying $x_{e}=k$. When $e \in \delta\left(V_{i}, V_{j}\right)$ for some $i, j$, we define $S_{e}=S_{\ell}-\chi^{e_{i j}}+\chi^{e}$, where $S_{\ell}$ is $S_{1}$ if $e \in \delta\left(V_{1}, V_{4}\right) \cup \delta\left(V_{2}, V_{3}\right)$ and $S_{2}$ otherwise. Affine independence comes because $S_{e}$ is the only point involving $e$.

## 数学代写|组合优化代写Combinatorial optimization代考|TDI Systems for Pk

Let $G$ be a series-parallel graph. In this section, we study the total dual integrality of systems describing $P_{k}(G)$. Due to length limitation, some of the proofs of the results below are omitted. They can be found in the appendix.

The following result characterizes series-parallel graphs in terms of TDIness of System (2).

Theorem 6. For $k>1$ odd and integer, System (2) is TDI if and only if $G$ is series-parallel.

Proof (sketch). We first prove that if $G$ is not series-parallel, then System (2) is not TDI. Indeed, every TDI system with integer right-hand side describes an integer polyhedron (Edmonds and Giles, 1977 ), but, when $G$ has a $K_{4}$-minor, System (2) describes a noninteger polyhedron (Chopra, 1994).

Let us sketch the other direction of the proof, that is, when the graph is series-parallel. We proceed by contradiction and consider a minimal counterexample $G$. First, we show that $G$ is simple and 2-connected. Then, we show that $G$ contains none of the following configurations.

Since the red vertices in the figure above have degree 2 in $G$, this contradicts Proposition $1 .$

For $k>1$, by Theorem $5, P_{k}(G)$ is a box-TDI polyhedron if and only if $G$ is series-parallel. Together with (Cook 1986, Corollary 2.5), this implies the following.

Corollary 2. For $k>1$ odd and integer, System (2) is box-TDI if and only if $G$ is series-parallel.The following theorem gives a TDI system for $P_{k}(G)$ when $G$ is series-parallel and $k$ is even.

## 数学代写|组合优化代写Combinatorial optimization代考|k-edge-connected Spanning Subgraph Polyhedron

(1) $\left{X(D)≥ķ 对于所有削减 D 的 G, X≥0\对。一种nd在H和nķ一世s这dd,P_{k}(G)一世sd和sCr一世b和db是:(2)\剩下{X(米)≥ķ+12d米−1 对于所有多切 米 的 G, X≥0.\对。吨H和一世nC一世d和nC和在和C吨这r这F一种F一种米一世l是F这F和一世s吨H和在和C吨这r\chi^{F}这F\mathbb{Z}^{E}s在CH吨H一种吨和‘sC这这rd一世n一种吨和一世s吨H和米在l吨一世pl一世C一世吨是这F和一世nFF这r一种ll和一世n和.小号一世nC和吨H和r和一世s一种b一世j和C吨一世这nb和吨在和和nF一种米一世l一世和s一种nd吨H和一世r一世nC一世d和nC和在和C吨这rs,在和在一世ll这F吨和n在s和吨H和s一种米和吨和r米一世n这l这G是F这rb这吨H.小号一世nC和吨H和一世nC一世d和nC和在和C吨这r这F一种米在l吨一世C在吨\delta\left(V_{1}, \ldots, V_{d_{M}}\right)一世s吨H和H一种lF−s在米这F吨H和一世nC一世d和nC和在和C吨这rs这F吨H和b这nds\delta\left(V_{1}\right), \ldots, \delta\left(V_{d_{M}}\right),在和C一种nd和d在C和一种n一种l吨和rn一种吨一世在和d和sCr一世p吨一世这n这FP_{2 h}(G)$。

$$\left{X(米)≥ķ2d米 对于所有多切 米 的 G, X≥0.\对。$$

（i）如果d米≥3， 然后X(d(在一世)∩d(在j))≤ķ+12对全部i \neq j \in\left{1, \ldots, d_{M}\right}i \neq j \in\left{1, \ldots, d_{M}\right}.
(二)G∖在一世为所有人连接一世=1,…,d米.

Chopra (1994) 给出了定义一个不等式的充分条件。以下命题是 (Chopra 1994, Theorem 2.4) 的直接结果。

## 有限元方法代写

tatistics-lab作为专业的留学生服务机构，多年来已为美国、英国、加拿大、澳洲等留学热门地的学生提供专业的学术服务，包括但不限于Essay代写，Assignment代写，Dissertation代写，Report代写，小组作业代写，Proposal代写，Paper代写，Presentation代写，计算机作业代写，论文修改和润色，网课代做，exam代考等等。写作范围涵盖高中，本科，研究生等海外留学全阶段，辐射金融，经济学，会计学，审计学，管理学等全球99%专业科目。写作团队既有专业英语母语作者，也有海外名校硕博留学生，每位写作老师都拥有过硬的语言能力，专业的学科背景和学术写作经验。我们承诺100%原创，100%专业，100%准时，100%满意。

## MATLAB代写

MATLAB 是一种用于技术计算的高性能语言。它将计算、可视化和编程集成在一个易于使用的环境中，其中问题和解决方案以熟悉的数学符号表示。典型用途包括：数学和计算算法开发建模、仿真和原型制作数据分析、探索和可视化科学和工程图形应用程序开发，包括图形用户界面构建MATLAB 是一个交互式系统，其基本数据元素是一个不需要维度的数组。这使您可以解决许多技术计算问题，尤其是那些具有矩阵和向量公式的问题，而只需用 C 或 Fortran 等标量非交互式语言编写程序所需的时间的一小部分。MATLAB 名称代表矩阵实验室。MATLAB 最初的编写目的是提供对由 LINPACK 和 EISPACK 项目开发的矩阵软件的轻松访问，这两个项目共同代表了矩阵计算软件的最新技术。MATLAB 经过多年的发展，得到了许多用户的投入。在大学环境中，它是数学、工程和科学入门和高级课程的标准教学工具。在工业领域，MATLAB 是高效研究、开发和分析的首选工具。MATLAB 具有一系列称为工具箱的特定于应用程序的解决方案。对于大多数 MATLAB 用户来说非常重要，工具箱允许您学习应用专业技术。工具箱是 MATLAB 函数（M 文件）的综合集合，可扩展 MATLAB 环境以解决特定类别的问题。可用工具箱的领域包括信号处理、控制系统、神经网络、模糊逻辑、小波、仿真等。

## 数学代写|组合优化代写Combinatorial optimization代考|On k-edge-connected Polyhedra

statistics-lab™ 为您的留学生涯保驾护航 在代写组合优化Combinatorial optimization方面已经树立了自己的口碑, 保证靠谱, 高质且原创的统计Statistics代写服务。我们的专家在代写组合优化Combinatorial optimization代写方面经验极为丰富，各种代写组合优化Combinatorial optimization相关的作业也就用不着说。

• Statistical Inference 统计推断
• Statistical Computing 统计计算
• (Generalized) Linear Models 广义线性模型
• Statistical Machine Learning 统计机器学习
• Longitudinal Data Analysis 纵向数据分析
• Foundations of Data Science 数据科学基础

## 数学代写|组合优化代写Combinatorial optimization代考|Box-TDIness in Series-Parallel Graphs

Totally dual integral systems – introduced in the late 70 ‘s – are strongly connected to min-max relations in combinatorial optimization (Schrijver, 1998). A rational system of linear inequalities $A x \geq b$ is totally dual integral (TDI) if the maximization problem in the linear programming duality:
$$\min \left{c^{\top} x: A x \geq b\right}=\max \left{b^{\top} y: A^{\top} y=c, y \geq \mathbf{0}\right}$$
admits an integer optimal solution for each integer vector $c$ such that the optimum is finite. Every rational polyhedron can be described by a TDI system (Giles and Pulleyblank, 1979). For instance, $\frac{1}{q} A x \geq \frac{1}{q} b$ is TDI for some positive $q$.

However,

only integer polyhedra can be described by TDI systems with integer right-hand side (Edmonds and Giles, 1984). TDI systems with only integer coefficients yield min-max results that have combinatorial interpretation.

A stronger property is the box-total dual integrality, where a system $A x \geq b$ is box-totally dual integral (box-TDI) if $A x \geq b, \ell \leq x \leq u$ is TDI for all rational vectors $\ell$ and $u$ (possibly with infinite components). General properties of such systems can be found in (Cook, 1986) and Chapter $22.4$ of (Schrijver, 1998). Note that, although every rational polyhedron ${x: A x \geq b}$ can be described by a TDI system, not every polyhedron can be described by a box-TDI system. A polyhedron which can be described by a box-TDI system is called a boxTDI polyhedron. As proved by Cook (1986), every TDI system describing such a polyhedron is actually box-TDI.

Recently, several new box-TDI systems were exhibited. Chen et al. (2008) characterized box-Mengerian matroid ports. Ding et al. (2017) characterized the graphs for which the TDI system of Cunningham and Marsh (1978) describing the matching polytope is actually box-TDI. Ding et al. (2018) introduced new subclasses of box-perfect graphs. Cornaz et al. (2019) provided several box-TDI systems in series-parallel graphs. For these graphs, Barbato et al. (2020) gave the box-TDI system for the flow cone having integer coefficients and the minimum number of constraints. Chen et al. (2009) provided a box-TDI system describing the 2-edge-connected spanning subgraph polyhedron for the same class of graphs.
In this paper, we are interested in integrality properties of systems related to $k$-edge-connected spanning subgraphs. Given a positive integer $k$, a $k$-edgeconnected spanning subgraph of a connected graph $G=(V, E)$ is a connected graph $H=(V, F)$, with $F$ a family of elements of $E$, that remains connected after the removal of any $k-1$ edges.

These objects model a kind of failure resistance of telecommunication networks. More precisely, they represent networks which remain connected when $k-1$ links fail. The underlying network design problem is the $k$-edge-connected spanning subgraph problem ( $k$-ECSSP): given a graph $G$, and positive edge costs, find a $k$-edge-connected spanning subgraph of $G$ of minimum cost. Special cases of this problem are related to classic combinatorial optimization problems. The 2-ECSSP is a well-studied relaxation of the traveling salesman problem (Erickson et al. 1987) and the 1-ECSSP is nothing but the well-known minimum spanning tree problem. While this latter is polynomial-time solvable, the $k$-ECSSP is NPhard for every fixed $k \geq 2$ (Garey and Johnson, 1979).

Different algorithms have been devised in order to deal with the $k$-ECSSP. Notable examples are branch-and-cut procedures (Cornaz et al. 2014), approximation algorithms (Gabow et al. 2009), Cutting plane algorithms Grötschel et al. (1992), and heuristics (Clarke and Anandalingam, 1995). Winter (1986) introduced a linear-time algorithm solving the 2-ECSSP on series-parallel graphs. Most of these algorithms rely on polyhedral considerations.

The $k$-edge-connected spanning subgraph polyhedron of $G$, hereafter denoted by $P_{k}(G)$, is the convex hull of all the $k$-edge-connected spanning subgraphs of $G$. Cornuéjols et al. (1985) gave a system describing $P_{2}(G)$ for series-parallel graphs.

## 数学代写|组合优化代写Combinatorial optimization代考|Definitions and Preliminary Results

Let $G=(V, E)$ be a loopless undirected graph. The graph $G$ is 2-connected if it remains connected whenever a vertex is removed. A 2-connected graph is called trivial if it is composed of a single edge. The graph obtained from two disjoint graphs by identifying two vertices, one of each graph, is called a 1 -sum. A subset of edges of $G$ is called a circuit if it induces a connected graph in which every vertex has degree 2 . Given a subset $U$ of $V$, the cut $\delta(U)$ is the set of edges having exactly one endpoint in $U$. A bond is a minimal nonempty cut. Given a partition $\left{V_{1}, \ldots, V_{n}\right}$ of $V$, the set of edges having endpoints in two distinct $V_{i}$ ‘s is called multicut and is denoted by $\delta\left(V_{1}, \ldots, V_{n}\right)$. We denote respectively by $\mathcal{M}{G}$ and $\mathcal{B}{G}$ the set of multicuts and the set of bonds of $G$. For every multicut $M$, there exists a unique partition $\left{V_{1}, \ldots, V_{d_{M}}\right}$ of vertices of $V$ such that $M=\delta\left(V_{1}, \ldots, V_{d_{M}}\right)$, and $G\left[V_{i}\right]$ – the graph induced by the vertices of $V_{i}$-is connected for all $i=1, \ldots, d_{M}$; we say that $d_{M}$ is the order of $M$.

We denote the symmetric difference of two sets $S$ and $T$ by $S \Delta T$. It is well-known that the symmetric difference of two cuts is a cut.

We denote by $K_{n}$ the complete graph on $n$ vertices, that is, the simple graph with $n$ vertices and one edge between each pair of distinct vertices.

A graph is series-parallel if its 2-connected components can be constructed from an edge by repeatedly adding edges parallel to an existing one, and subdividing edges, that is, replacing an edge by a path of length two. Duffin (1965) showed that series-parallel graphs are those having no $K_{4}$-minor. By construction, simple nontrivial 2-connected series-parallel graphs have at least one vertex of degree 2 .

Proposition 1. For a simple nontrivial 2-connected series-parallel graph, at least one of the following holds:
(a) two vertices of degree 2 are adjacent,
(b) a vertex of degree 2 belongs to a circuit of length 3,
(c) two vertices of degree 2 belong to a same circuit of length 4 .
Proof. We proceed by induction on the number of edges. The base case is $K_{3}$ for which (a) holds.

Let $G$ be a simple 2-connected series-parallel graph such that for every simple, 2-connected series-parallel graph with fewer edges at least one among (a), (b), and (c) holds. Since $G$ is simple, it can be built from a graph $H$ by subdividing an edge $e$ into a path $f, g$. Let $v$ be the vertex of degree 2 added with this operation. By the induction hypothesis, either $H$ is not simple, or one among (a), (b), and (c) holds for $H$.

Let first suppose that $H$ is not simple, then, by $G$ being simple, $e$ is parallel to exactly one edge $e_{0}$. Hence, $e_{0}, f, g$ is a circuit of $G$ length 3 containing $v$, hence (b) holds for $G$.

From now on, suppose that $H$ is simple. If (a) holds for $H$, then it holds for $G$.

Suppose that (b) holds for $H$, that is, in $H$ there exists a circuit $C$ of length 3 containing a vertex $w$ of degree 2 . Without loss of generality, we suppose that

$e \in C$, as otherwise (b) holds for $G$. By subdividing $e$, we obtain a circuit of length 4 containing $v$ and $w$, and hence (c) holds for $G$.

At last, suppose that (c) holds for $H$, that is, $H$ has a circuit $C$ of length 4 containing two vertices of degree 2. Without loss of generality, we suppose that $e \in C$, as otherwise (c) holds for $G$. By subdividing $e$, we obtain a circuit of length 5 containing three vertices of degree 2 . Then, at least two of them are adjacent, and so (a) holds for $G$.

## 数学代写|组合优化代写Combinatorial optimization代考|Box-Total Dual Integrality

Let $A \in \mathbb{R}^{m \times n}$ be a full row rank matrix. This matrix is equimodular if all its $m \times m$ non-zero determinants have the same absolute value. The matrix $A$ is face-defining for a face $F$ of a polyhedron $P \subseteq \mathbb{R}^{n}$ if aff $(F)=\left{x \in \mathbb{R}^{n}: A x=b\right}$ for some $b \in \mathbb{R}^{m}$. Such matrices are the face-defining matrices of $P$.

Theorem 1 (Chervet et al. (2020)). Let P be a polyhedron, then the following statements are equivalent:
(i) $P$ is box-TDI.
(ii) Every face-defining matrix of $P$ is equimodular.
(iii) Every face of $P$ has an equimodular face-defining matrix.
The equivalence of conditions (ii) and (iii) stems from the following observation.
Observation 1 (Chervet et al. (2020)). Let $F$ be a face of a polyhedron. If a face-defining matrix of $F$ is equimodular, then so are all face-defining matrices of $F$.

Observation 2. Let $A \in \mathbb{R}^{I \times J}$ be a full row rank matrix, $j \in J$, c be a column of $A$, and $\mathbf{v} \in \mathbb{R}^{I}$. If $A$ is equimodular, then so are:
(i) $[A \mathbf{c}]$,
(ii) $\left[\begin{array}{c}A \ \pm \chi^{j}\end{array}\right]$ if it is full row rank,
(iii) $\left[\begin{array}{cc}A & \mathbf{v} \ \mathbf{0}^{\top} & \pm 1\end{array}\right]$
and (iv) $\left[\begin{array}{cc}A & 0 \ \pm \chi^{j} & \pm 1\end{array}\right]$

Observation 3 (Chervet et al. (2020)). Let $P \subseteq \mathbb{R}^{n}$ be a polyhedron and let $F={x \in P: B x=b}$ be a face of $P$. If $B$ has full row rank and $n-\operatorname{dim}(F)$ rows, then $B$ is face-defining for $F$.

## 数学代写|组合优化代写Combinatorial optimization代考|Box-TDIness in Series-Parallel Graphs

70 年代后期引入的完全对偶积分系统与组合优化中的最小-最大关系密切相关（Schrijver，1998 年）。线性不等式的合理系统一种X≥b如果线性规划对偶中的最大化问题是完全对偶积分 (TDI)：
\min \left{c^{\top} x: A x \geq b\right}=\max \left{b^{\top} y: A^{\top} y=c, y \geq \mathbf {0}\右}\min \left{c^{\top} x: A x \geq b\right}=\max \left{b^{\top} y: A^{\top} y=c, y \geq \mathbf {0}\右}

## 数学代写|组合优化代写Combinatorial optimization代考|Definitions and Preliminary Results

（a）两个 2 次顶点相邻，
（b）一个 2 次顶点属于长度为 3 的回路，
(c) 两个度数为 2 的顶点属于长度为 4 的同一回路。

## 数学代写|组合优化代写Combinatorial optimization代考|Box-Total Dual Integrality

(i)磷是box-TDI。
(ii) 每个人脸定义矩阵磷是等模的。
(iii) 每一张脸磷具有等模人脸定义矩阵。

(i)[一种C],
(ii)[一种 ±χj]如果它是全行排名，
（iii）[一种在 0⊤±1]
(iv)[一种0 ±χj±1]

## 有限元方法代写

tatistics-lab作为专业的留学生服务机构，多年来已为美国、英国、加拿大、澳洲等留学热门地的学生提供专业的学术服务，包括但不限于Essay代写，Assignment代写，Dissertation代写，Report代写，小组作业代写，Proposal代写，Paper代写，Presentation代写，计算机作业代写，论文修改和润色，网课代做，exam代考等等。写作范围涵盖高中，本科，研究生等海外留学全阶段，辐射金融，经济学，会计学，审计学，管理学等全球99%专业科目。写作团队既有专业英语母语作者，也有海外名校硕博留学生，每位写作老师都拥有过硬的语言能力，专业的学科背景和学术写作经验。我们承诺100%原创，100%专业，100%准时，100%满意。

## MATLAB代写

MATLAB 是一种用于技术计算的高性能语言。它将计算、可视化和编程集成在一个易于使用的环境中，其中问题和解决方案以熟悉的数学符号表示。典型用途包括：数学和计算算法开发建模、仿真和原型制作数据分析、探索和可视化科学和工程图形应用程序开发，包括图形用户界面构建MATLAB 是一个交互式系统，其基本数据元素是一个不需要维度的数组。这使您可以解决许多技术计算问题，尤其是那些具有矩阵和向量公式的问题，而只需用 C 或 Fortran 等标量非交互式语言编写程序所需的时间的一小部分。MATLAB 名称代表矩阵实验室。MATLAB 最初的编写目的是提供对由 LINPACK 和 EISPACK 项目开发的矩阵软件的轻松访问，这两个项目共同代表了矩阵计算软件的最新技术。MATLAB 经过多年的发展，得到了许多用户的投入。在大学环境中，它是数学、工程和科学入门和高级课程的标准教学工具。在工业领域，MATLAB 是高效研究、开发和分析的首选工具。MATLAB 具有一系列称为工具箱的特定于应用程序的解决方案。对于大多数 MATLAB 用户来说非常重要，工具箱允许您学习应用专业技术。工具箱是 MATLAB 函数（M 文件）的综合集合，可扩展 MATLAB 环境以解决特定类别的问题。可用工具箱的领域包括信号处理、控制系统、神经网络、模糊逻辑、小波、仿真等。

## 数学代写|组合优化代写Combinatorial optimization代考|Preliminaries

statistics-lab™ 为您的留学生涯保驾护航 在代写组合优化Combinatorial optimization方面已经树立了自己的口碑, 保证靠谱, 高质且原创的统计Statistics代写服务。我们的专家在代写组合优化Combinatorial optimization代写方面经验极为丰富，各种代写组合优化Combinatorial optimization相关的作业也就用不着说。

• Statistical Inference 统计推断
• Statistical Computing 统计计算
• (Generalized) Linear Models 广义线性模型
• Statistical Machine Learning 统计机器学习
• Longitudinal Data Analysis 纵向数据分析
• Foundations of Data Science 数据科学基础

## 数学代写|组合优化代写Combinatorial optimization代考|Preliminaries

The main result of this paper is the following theorem.
Theorem 2. Let $G=(V, A)$ be a directed graph, then $P C_{p}(G)$ is integral for any integer $p$ if and only if
(C1) it does not contain as a subgraph any of the graphs $H_{1}, H_{2}, H_{3}, H_{4}, H_{5}$, $H_{6}$ of Fig. 1, and
(C2) it does not contain a non-directed $g$-odd $Y$-cycle $C$ with an arc $(u, v)$ with both $u$ and $v$ not in $V(C)$.

Given a directed graph $G=(V, A)$, a subgraph induced by the nodes $v_{1}, \ldots, v_{r}$ of $D$ is called a bidirected cycle if the only arcs in this induced subgraph are $\left(v_{i}, v_{i+1}\right)$ and $\left(v_{i+1}, v_{i}\right)$, for $i=1, \ldots, r$, with $v_{r+1}=v_{1}$. We denote it by $B I C_{r}$.

For a directed graph $G=(V, A)$ and an arc $(u, v) \in A$, define $G(u, v)$ to be the graph obtained by removing $(u, v)$ from $G$, and adding a new arc $\left(u, v^{\prime}\right)\left(v^{\prime}\right.$ is a new pendent node). The rest of this section is devoted to definitions with respect to a feasible point in $P C_{p}(G)$.

Definition 3. A vector $(x, y) \in \mathbb{R}^{|A|+|V|}$ will be denoted by $z$, i.e., $z(u)=y(u)$ for all $u \in V$ and $z(u, v)=x(u, v)$ for all $(u, v) \in A$. Given a vector $z$ and $a$ labeling function $l: V \cup A \rightarrow{-1,0,1}$, we define a new vector $z_{l}$ from $z$ as follows:
$$\begin{gathered} z_{l}(u)=z(u)+l(u) \epsilon, \text { for all } u \in V, \text { and } \ z_{l}(u, v)=z(u, v)+l(u, v) \epsilon, \text { for all }(u, v) \in A \end{gathered}$$
where $\epsilon$ is a sufficiently small positive scalar. When we assign labels to some nodes and arcs without specifying the labels of the remaining nodes and arcs, it means that they are assigned the label zero.

Definition 4. When dealing with a vector $z \in P C_{p}(G)$, we say that the arc $(u, v)$ is tight if $z(u, v)=z(v)$. Also we say that an odd directed cycle $C$ is tight if $z(A(C))=(|A(C)|-1) / 2$.

## 数学代写|组合优化代写Combinatorial optimization代考|The Proof of Theorem 2

We will sketch quickly the necessity part of the proof. With each of the graphs $H_{1}, H_{2}, H_{3}$ and $H_{6}$ in Fig. 1 we show a fractional extreme point of $P C_{3}(G)$ when $G$ is restricted to these graphs. The graphs $H_{4}$ and $H_{5}$ show an extreme point of $P C_{2}(G)$. The numbers near the nodes correspond to $y$ variables. The $x$ variables take the value $\frac{1}{2}$ for $H_{1}, H_{2}$ and $H_{4}$. For the graphs $H_{3}, H_{5}$ and $H_{6}$ the arcs take the value $\frac{1}{3}$, except the arc in the right in $H_{6}$ that takes the value $\frac{2}{3}$.

To prove necessity we just have to notice that the extreme points for the subgraphs $H_{i}$, for $i=1, \ldots, 6$, in Fig. 1 may be extended to extreme points for any graph containing these subgraphs by setting each remaining node variable to one and each remaining arc variable to zero. For condition (C2) when the graph contains a non-directed g-odd $Y$-cycle $C$ with an arc $(u, v)$ having both nodes $u$ and $v$ not in $C$, we construct an extreme point of $P C(G)$ where $p=$ $\frac{|C|+|C|+1}{2}+|V|-|V(C)|-1$ as follows. All the nodes in $C$ take the value 0 , the nodes in $\bar{C}$ and $\hat{C}$ with the node $u$ take the value $\frac{1}{2} ;$ all the arcs in $C$ with $(u, v)$ take the value $\frac{1}{2}$. All other nodes take the value 1 and the other arcs take the value 0, except for each unique arc leaving each node in $\hat{C}$ (see the definition of a $Y$-cycle) they take the value $\frac{1}{2}$. One way to see that these are indeed extreme points is to start adding $\epsilon$ to one of the components and try to keep satisfying as equation the same constraints that the original vector satisfies as equation. First we conclude that we have to add or subtract $\epsilon$ to other components and this leads to the violation of Eq. (1) or to the impossibility of keeping tight the inequality that are satisfied as equation.

The rest of this section is devoted to the sufficiency part. Denotes by Pair $(G)$ the set of pair of nodes ${u, v}$ such that both arcs $(u, v)$ and $(v, u)$ exist. The proof of this theorem will be done by induction on the number of $|P a i r(G)|$. This result has been proved in [3] for oriented graphs, that is when $|P a i r(G)|=0$. This case is the starting point of the induction. Assume that Theorem 2 is true for any directed graph $H$ with $|P a i r(H)| \leq m$ and let us show that it holds for any directed graph $G$ with $|\operatorname{Pair}(G)|=m+1$. Let $G=(V, A)$ be a directed graph with $|P a i r(G)|=m+1 \geq 1$ satisfying conditions (C1) and (C2) of Theorem 2. Suppose the contrary, that is $P C_{p}(G)$ is not integral. Let $\bar{z}$ be a fractional extreme point of $P C_{p}(G)$. Next we will give some useful lemmas and then in Subsect. $3.1$ and $3.2$ the proof is completed. In Subsect. $3.1$ we show the theorem when there is no g-odd $Y$-cycle and in Subsect. $3.2$ we complete the proof when such a cycle exists.

## 数学代写|组合优化代写Combinatorial optimization代考|G Does Not Contain a Non-directed g-Odd Y -Cycle

When we have two arcs $(u, v)$ and $(v, u)$, from Lemma 3, the graph $G(u, v)$ satisfies condition (C1), which is not the case for condition (C2), even when $G$ does not contain a non-directed g-odd $Y$-cycle. For example we may have a g-odd cycle $C$ which is not a Y-cycle and an arc $(s, t)$ with both $s$ and $t$ not in $V(C)$. Now if we have an arc $(u, v)$ in $A(C)$ and $(v, u) \in A \backslash A(C)$, and if $v \in \hat{C}$ and $u \in C$ this same cycle may become a Y-cycle in $G(v, u)$ and so with the arc $(s, t)$ condition $(\mathrm{C} 2)$ is violated.

Next we will show that we may always find a pair of $\operatorname{arcs}(u, v)$ and $(v, u)$ where at least one of the graphs $G(u, v)$ or $G(v, u)$ satisfies (C2).

Lemma 8. Let $P=v_{1}, \ldots, v_{k}$ a maximal bidirected path, different from a bidirected cycle. We have the following

(i) If $G\left(v_{k}, v_{k-1}\right)$ contains a non-directed $g$-odd $Y$-cycle $C$, then the unique arc leaving $v_{k}$ is $\left(v_{k}, v_{k-1}\right)$,
(ii) If $G\left(v_{k-1}, v_{k}\right)$ contains a non-directed $g$-odd $Y$-cycle $C$, then there is at most one another arc leaving $v_{k-1}$ which is $\left(v_{k-1}, v_{k-2}\right)$.

Let $P=v_{1}, \ldots, v_{k}$ be a maximal bidirected path. From Lemma 4 the extremities of $P$ cannot coincide, that is $P$ is not a bidirected cycle. We will treat two cases (1) none of the arcs $\left(v_{k-1}, v_{k}\right)$ and $\left(v_{k}, v_{k-1}\right)$ belong to an odd directed cycle tight for $\bar{z}$ and of size at least five, (2) at least one of these arcs belong to such a cycle.

Case 1. None of the arcs $\left(v_{k-1}, v_{k}\right)$ and $\left(v_{k}, v_{k-1}\right)$ belong to an odd directed cycle of size at least five. From the lemma above it is easy to see that at least one of the graphs $G\left(v_{k}, v_{k-1}\right)$ or $G\left(v_{k-1}, v_{k}\right)$ does not contain a g-odd $Y$-cycle. In fact, assume that both graphs contain a g-odd $Y$-cycle. When $G\left(v_{k-1}, v_{k}\right)$ contains a g-odd $Y$-cycle $C$, we must have $v_{k} \in \dot{C}$. But this is impossible since Lemma 8 (i) implies that $\left(v_{k}, v_{k-1}\right)$ is the unique arc leaving $v_{k}$. Therefore, we only need to treat the following three cases, ordered as follows.

## 数学代写|组合优化代写Combinatorial optimization代考|Preliminaries

(C1) 它不包含任何图作为子图H1,H2,H3,H4,H5, H6图 1 和
(C2) 它不包含非定向G-奇怪的是-循环C带弧线(在,在)既在和在不在在(C).

## 数学代写|组合优化代写Combinatorial optimization代考|G Does Not Contain a Non-directed g-Odd Y -Cycle

(一) 如果G(在ķ,在ķ−1)包含一个非定向G-奇怪的是-循环C，则唯一弧离开在ķ是(在ķ,在ķ−1),
(ii) 如果G(在ķ−1,在ķ)包含一个非定向G-奇怪的是-循环C, 那么最多有一个弧离开在ķ−1这是(在ķ−1,在ķ−2).

## 有限元方法代写

tatistics-lab作为专业的留学生服务机构，多年来已为美国、英国、加拿大、澳洲等留学热门地的学生提供专业的学术服务，包括但不限于Essay代写，Assignment代写，Dissertation代写，Report代写，小组作业代写，Proposal代写，Paper代写，Presentation代写，计算机作业代写，论文修改和润色，网课代做，exam代考等等。写作范围涵盖高中，本科，研究生等海外留学全阶段，辐射金融，经济学，会计学，审计学，管理学等全球99%专业科目。写作团队既有专业英语母语作者，也有海外名校硕博留学生，每位写作老师都拥有过硬的语言能力，专业的学科背景和学术写作经验。我们承诺100%原创，100%专业，100%准时，100%满意。

## MATLAB代写

MATLAB 是一种用于技术计算的高性能语言。它将计算、可视化和编程集成在一个易于使用的环境中，其中问题和解决方案以熟悉的数学符号表示。典型用途包括：数学和计算算法开发建模、仿真和原型制作数据分析、探索和可视化科学和工程图形应用程序开发，包括图形用户界面构建MATLAB 是一个交互式系统，其基本数据元素是一个不需要维度的数组。这使您可以解决许多技术计算问题，尤其是那些具有矩阵和向量公式的问题，而只需用 C 或 Fortran 等标量非交互式语言编写程序所需的时间的一小部分。MATLAB 名称代表矩阵实验室。MATLAB 最初的编写目的是提供对由 LINPACK 和 EISPACK 项目开发的矩阵软件的轻松访问，这两个项目共同代表了矩阵计算软件的最新技术。MATLAB 经过多年的发展，得到了许多用户的投入。在大学环境中，它是数学、工程和科学入门和高级课程的标准教学工具。在工业领域，MATLAB 是高效研究、开发和分析的首选工具。MATLAB 具有一系列称为工具箱的特定于应用程序的解决方案。对于大多数 MATLAB 用户来说非常重要，工具箱允许您学习应用专业技术。工具箱是 MATLAB 函数（M 文件）的综合集合，可扩展 MATLAB 环境以解决特定类别的问题。可用工具箱的领域包括信号处理、控制系统、神经网络、模糊逻辑、小波、仿真等。

## 数学代写|组合优化代写Combinatorial optimization代考|Some Families of Split Graphs

statistics-lab™ 为您的留学生涯保驾护航 在代写组合优化Combinatorial optimization方面已经树立了自己的口碑, 保证靠谱, 高质且原创的统计Statistics代写服务。我们的专家在代写组合优化Combinatorial optimization代写方面经验极为丰富，各种代写组合优化Combinatorial optimization相关的作业也就用不着说。

• Statistical Inference 统计推断
• Statistical Computing 统计计算
• (Generalized) Linear Models 广义线性模型
• Statistical Machine Learning 统计机器学习
• Longitudinal Data Analysis 纵向数据分析
• Foundations of Data Science 数据科学基础

## 数学代写|组合优化代写Combinatorial optimization代考|Some Families of Split Graphs

A graph $G=(C \cup S, E)$ is a split graph if its node set can be partitioned into a clique $C$ and a stable set $S$. Split graphs are closed under taking complements and form the complementary core of chordal graphs since $G$ is a split graph if and only if $G$ and $\bar{G}$ are chordal or if and only if $G$ is $\left(C_{4}, \bar{C}{4}, C{5}\right)$-free [11].
Our aim is to study LTD-sets in some families of split graphs having a regular structure from a polyhedral point of view. Complete Split Graphs. A complete split graph is a split graph where all edges between $C$ and $S$ are present. Complete split graphs can be seen as special case of complete multi-partite graphs studied in Sect. 3. In fact, a complete split graph is a clique if $|S|=1$, a star if $|C|=1$, and a crown if $|C|=2$, see Fig. 3(a), (b). Otherwise, the graph can be seen as a complete multi-partite graph where all parts but one have size 1 , i.e. as $K_{n_{1}, n_{2}, \ldots, n_{p}}$ with $n_{1}=\cdots=n_{p-1}=1$ and $n_{p} \geq 2$ such that $U_{1} \cup \cdots \cup U_{p-1}$ induce the clique $C$ and $U_{p}$ the stable set $S$. Hence, we directly conclude from Lemma 3 and Corollary 5 :

Corollary 6. Let $G=(C \cup S, E)$ be a complete split graph.
(a) If $|S|=1$, then $G$ is a clique,
$$C_{X}(G)=M\left(\mathcal{R}{|C|+1}^{2}\right)$$ and $\gamma{X}(G)=|C|$ for $X \in{O L D, L T D}$.
(b) If $|C|=1$, then $G$ is a star,
$$C_{L T D}(G)=\left(\begin{array}{c|lll} 1 & 0 & \ldots & 0 \ \hline 0 & & \ \vdots & M\left(\mathcal{R}{|S|}^{2}\right) \ 0 & \end{array}\right)$$ and $\gamma{L T D}(G)=|S|$.
(c) Otherwise, we have
$$C_{L T D}(G)=\left(\begin{array}{cc} M\left(\mathcal{R}{|C|}^{2}\right) & 0 \ 0 & M\left(\mathcal{R}{|S|}^{2}\right) \end{array}\right)$$
and $\gamma_{L T D}(G)=|S|+|C|-2$.
Headless Spiders. A headless spider is a split graph with $C=\left{c_{1}, \ldots, c_{k}\right}$ and $S=\left{s_{1}, \ldots, s_{k}\right}$; it is thin (resp. thick) if $s_{i}$ is adjacent to $c_{j}$ if and only if $i=j$ (resp. $i \neq j$ ), see Fig. 3(c), (d) for illustration. Clearly, the complement of a thin spider is a thick spider, and vice-versa. It is easy to see that for $k=2$, the path $P_{4}$ equals the thin and thick headless spider. Moreover, it is easy to check that headless spiders are twin-free.

A thick headless spider with $k=3$ equals the 3 -sun $S_{3}$ and it is easy to see that $\gamma_{O L D}\left(S_{3}\right)=4$ and $\gamma_{L T D}\left(S_{3}\right)=3$ holds. To describe the clutters for $k \geq 4$, we use the following notations. Let $J_{n}$ denote the $n \times n$ matrix having 1-entries only and $I_{n}$ the $n \times n$ identity matrix. Furthermore, let $J_{n-1, n}(i)$ denote a matrix s.t. its $i$-th column has 0 -entries only and removing the $i$-th column results in $J_{n-1}$, and $I_{n-1, n}(j)$ denote a matrix s.t. its $j$-th column has 1 -entries only and removing the $j$-th column results in $I_{n-1}$.

## 数学代写|组合优化代写Combinatorial optimization代考|Concluding Remarks

In this paper, we proposed to study the $O L D$ – and $L T D$-problem from a polyhedral point of view, motivated by promising polyhedral results for the $I D$-problem [2-5]. That way, we were able to provide closed formulas for the LTD-numbers of all kinds of complete $p$-partite graphs (Sect. 3), and for the studied families of split graphs as well as the $O L D$-numbers of thin and thick headless spiders (Sect. 4).

In particular, if we have the same clutter matrix for two different $X$-problems, then we can conclude that every solution of one problem is also a solution for the other problem, and vice versa, such that the two $X$-polyhedra coincide and the two $X$-numbers are equal. This turned out to be the case for

• complete bipartite graphs as $C_{I D}\left(K_{m, n}\right)=C_{L T D}\left(K_{m, n}\right)$ holds by Lemma 2 and results from [2],
• thin headless spiders $G$ as $C_{O L D}(G)=C_{L T D}(G)$ holds by Lemma $5 .$
Furthermore, we were able to provide the complete facet descriptions of
• the LTD-polyhedra for all complete $p$-partite graphs (including complete split graphs) and for thin headless spiders (see Sect. 3 and Lemma 5),
• the $O L D$-polyhedra of cliques, thin and thick headless spiders (see Corollary 5 and Sect. 4).

The complete descriptions of some $X$-polyhedra also provide us with information about the relation between $Q^{}\left(C_{X}(G)\right)$ and its linear relaxation $Q\left(C_{X}(G)\right)$. A matrix $M$ is ideal if $Q^{}(M)=Q(M)$. For any nonideal matrix, we can evaluate how far $M$ is from being ideal by considering the inequalties that have to be added to $Q(M)$ in order to obtain $Q^{}(M)$. With this purpose, in [1], a matrix $M$ is called rank-ideal if only $0 / 1$-valued constraints have to be added to $Q(M)$ to obtain $Q^{}(M)$. From the complete descriptions obtained in Sect. 3 and Sect. 4 , we conclude:

Corollary 9. The LTD-clutters and OLD-clutters of thin headless spiders are ideal for all $k \geq 3$.

Corollary 10. The LTD-clutters of all complete p-partite graphs and the $O L D$ clutters of cliques and thick headless spiders are rank-ideal.

Finally, the LTD-clutters of thick headless spiders have a more complex structure such that also a facet description of the LTD-polyhedra is more involved. However, using polyhedral arguments, is was possible to establish that $k-1$ is a lower bound for the cardinality of any LTD-set. Exhibiting an LTD-set of size $k-1$ thus allowed us to deduce the exact value of the $L T D$-number of thick headless spiders (Theorem 3 ).

This demonstrates how the polyhedral approach can be applied to find $X$ sets of minimum size for special graphs $G$, by determining and analyzing the $X$-clutters $C_{X}(G)$, even in cases where no complete description of $P_{X}(G)$ is known yet.

As future lines of research, we plan to work on a complete description of the LTD-polyhedra of thick headless spiders and to apply similar and more advanced techniques for other graphs in order to obtain either $X$-sets of minimum size or strong lower bounds stemming from linear relaxations of the $X$-polyhedra, enhanced by suitable cutting planes.

## 数学代写|组合优化代写Combinatorial optimization代考|Mourad Ba¨ıou1 and Francisco Barahona2

This paper follows the study of the classical linear formulation for the $p$-median problem started in [1-3]. To avoid repetitions, we refer to [1] for a more detailed introduction on the $p$-median problem.

Let $G=(V, A)$ a directed graph not necessarily connected, where each arc $(u, v) \in A$ has an associated cost $c(u, v)$. Here we make a difference between oriented and directed graphs. In oriented graphs at most one of the the arcs $(u, v)$ or $(v, u)$ exist, while in directed graphs we may have both arcs $(u, v)$ and $(v, u)$. The $p$-median problem $(p \mathrm{MP})$ consists of selecting $p$ nodes, usully called centers, and then assign each nonselected node along an arc to a selected node. The goal is to select $p$ nodes that minimize the sum of the costs yielded by the assignment of the nonselected nodes. If the number of centers is not fixed and in stead we have costs associated with nodes, then we get the well known facility location problem.

If we associate the variables $y$ to the nodes, and the variables $x$ to the arcs, the following is the classical linear relaxation of the $p \mathrm{MP}$. If we remove equality (1), then we get a linear relaxation of the facility location problem.

\begin{aligned} &\sum_{v \in V} y(v)=p, \ &y(u)+\sum_{v:(u, v) \in A} x(u, v)=1 \quad \forall u \in V, \ &x(u, v) \leq y(v) \quad \forall(u, v) \in A, \ &y(v) \geq 0 \quad \forall v \in V, \ &x(u, v) \geq 0 \quad \forall(u, v) \in A . \end{aligned}
Call $p \mathrm{MP}(G)$ the $p$-median polytope, that is the convex hull of integer solutions satisfying (1)-(5).

Now we will introduced a class of valid inequalities based on odd directed cycles. For this we need some additional definitions. A simple cycle $C$ is an ordered sequence $v_{0}, a_{0}, v_{1}, a_{1}, \ldots, a_{t-1}, v_{t}$, where
$-v_{i}, 0 \leq i \leq t-1$, are distinct nodes,

• either $v_{i}$ is the tail of $a_{i}$ and $v_{i+1}$ is the head of $a_{i}$, or $v_{i}$ is the head of $a_{i}$ and $v_{i+1}$ is the tail of $a_{i}$, for $0 \leq i \leq t-1$, and
$-v_{0}=v_{t}$.
Let $V(C)$ and $A(C)$ denote the nodes and the arcs of a simple cycle $C$, respectively. By setting $a_{t}=a_{0}$, we partition the vertices of $C$ into three sets: $\hat{C}, \dot{C}$ and $\vec{C}$. Each node $v$ is incident to two arcs $a^{\prime}$ and $a^{\prime \prime}$ of $C$. If $v$ is the head (resp. tail) of both arcs $a^{\prime}$ and $a^{\prime \prime}$ then $v$ is in $\hat{C}$ (resp. $\dot{C}$ ) and if $v$ is the head of one of them and a tail of the other, then $v$ is in $\tilde{C}$. Notice that $|\hat{C}|=|\dot{C}| . \mathrm{A}$ cycle will be called $g$-odd if $|\tilde{C}|+|\hat{C}|$ is odd, that is the number of nodes that are heads of some arcs in $C$ is odd. Otherwise it will be called $g$-even. A cycle $C$ with $V(C)=\tilde{C}$ is a directed cycle, otherwise it is called a non-directed cycle. Notice that the notion of g-odd (g-even) cycles generalizes the notion of odd (even) directed cycles, that is why we use the letter ” $\mathrm{g}$ “.

## 数学代写|组合优化代写Combinatorial optimization代考|Some Families of Split Graphs

This provides an alternative proof for the result given in [14].

## 数学代写|组合优化代写Combinatorial optimization代考|Locating Total-Dominating Sets in Graphs

• 一个识别码（ID），如果它是一个支配集，并且ñ[一世]∩C≠ñ[j]∩C, 对于不同的一世,j∈在[15];
• 一个开放的定位支配集（OLD），如果它是一个全支配集并且ñ(一世)∩C≠ñ(j)∩C, 对于不同的一世,j∈在[19];
• 一个定位总支配集（LTD），如果它是一个总支配集，并且ñ(一世)∩ C≠ñ(j)∩C, 对于不同的一世,j∈在−C[13].

C大号吨D(G)≤C这大号D(G)

## 数学代写|组合优化代写Combinatorial optimization代考|Polyhedra Associated to OLD- and LT D-Sets

(a) 让G既没有孤立节点也没有假孪生。C⊆在是一个旧集当且仅当C与

(二)C⊆在是一个 LTD 集当且仅当C与大号吨D1ñ(一世)对全部一世∈在,

$$P_{X}(G)=Q^{}\left(M_{X}(G)\right)=\operatorname{conv}\left{\mathbf{x} \in \mathbb{Z }{+}^{|V|}: M{X}(G) \mathbf{x} \geq 1\right }$$
X- 多面体X∈这大号D,大号吨D. 我们首先解决两个多面体的维度。它从巴拉斯和ñG[7]一个覆盖多面体的集合问(米)是全维的当且仅当矩阵米每行至少有两个。

## 数学代写|组合优化代写Combinatorial optimization代考|Complete p-Partite Graphs

X(在′)≥|在′|−q+1

C大号吨D(ķ1,n)=(100…0 0 ⋮米(Rn2)).

C大号吨D(ķ米,n)=(米(R米2)0 0米(Rn2)).

1. X(C)≥|C|−1对于所有非空C⊆一种,
2. X(C)≥|C|−1对于所有非空C⊆乙.
而且，C大号吨D(ķ米,n)=|在|−2=米+n−2.
这为 [14] 中给出的结果提供了另一种证明。

## 有限元方法代写

tatistics-lab作为专业的留学生服务机构，多年来已为美国、英国、加拿大、澳洲等留学热门地的学生提供专业的学术服务，包括但不限于Essay代写，Assignment代写，Dissertation代写，Report代写，小组作业代写，Proposal代写，Paper代写，Presentation代写，计算机作业代写，论文修改和润色，网课代做，exam代考等等。写作范围涵盖高中，本科，研究生等海外留学全阶段，辐射金融，经济学，会计学，审计学，管理学等全球99%专业科目。写作团队既有专业英语母语作者，也有海外名校硕博留学生，每位写作老师都拥有过硬的语言能力，专业的学科背景和学术写作经验。我们承诺100%原创，100%专业，100%准时，100%满意。

## MATLAB代写

MATLAB 是一种用于技术计算的高性能语言。它将计算、可视化和编程集成在一个易于使用的环境中，其中问题和解决方案以熟悉的数学符号表示。典型用途包括：数学和计算算法开发建模、仿真和原型制作数据分析、探索和可视化科学和工程图形应用程序开发，包括图形用户界面构建MATLAB 是一个交互式系统，其基本数据元素是一个不需要维度的数组。这使您可以解决许多技术计算问题，尤其是那些具有矩阵和向量公式的问题，而只需用 C 或 Fortran 等标量非交互式语言编写程序所需的时间的一小部分。MATLAB 名称代表矩阵实验室。MATLAB 最初的编写目的是提供对由 LINPACK 和 EISPACK 项目开发的矩阵软件的轻松访问，这两个项目共同代表了矩阵计算软件的最新技术。MATLAB 经过多年的发展，得到了许多用户的投入。在大学环境中，它是数学、工程和科学入门和高级课程的标准教学工具。在工业领域，MATLAB 是高效研究、开发和分析的首选工具。MATLAB 具有一系列称为工具箱的特定于应用程序的解决方案。对于大多数 MATLAB 用户来说非常重要，工具箱允许您学习应用专业技术。工具箱是 MATLAB 函数（M 文件）的综合集合，可扩展 MATLAB 环境以解决特定类别的问题。可用工具箱的领域包括信号处理、控制系统、神经网络、模糊逻辑、小波、仿真等。