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

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

We can solve IMCFP instances by simply formulating them as the Mixed-Integer Linear Program in Sect. $3.1$ and solving them using an off-the-shelf solver. By the polynomial number of constraints and variables of our formulation, we know that the decision version of IMCFP is in NP. Although the MCFP is polynomialtime solvable, our IMCFP formulation introduces the need of binary variables to ensure optimality among the different scenarios, meaning it is still an open question whether IMCFP is NP-complete or not. To solve all the following instances, we solved the IMCFP model with the MILP solver IBM CPLEX $12.6$ with default settings and a time limit of $1200 \mathrm{CPU}$ seconds on a personal computer (Intel Core i7-6820HQ $2.70 \mathrm{GHz}, 16$ GB DDR3 RAM). All graphs used in the following experiments are based on the topology of the Paris subway network, often restricted to the left bank. Therefore, each node represents a connection between one or more different metro lines, and each arc represents a section of a line. The network is strongly connected, meaning we can generate complete sets of demands $(|K|=(|V|-1)|V|)$. The demand value for each commodity $k \in K$ is an integer uniformly chosen in the interval $[1,10]$.

Firstly, to evaluate the prediction performance of the proposed formulations, we generated integer capacities for the MCFP in the interval $[1,15]$ and then calculated an optimal solution of MCFP for each scenario of demands, keeping the same capacities $C$ among them. It allows us to give the total configuration of loads $\ell_a^s$ and $K^s$ as input where an optimal solution with zero $\Delta$ value exists. This let us compare the computed capacities in $A \backslash A^{\prime}$, with those we chose to construct our instances of MCFP (the generated ones). Secondly, we generated $\ell_a^{\lrcorner}, K^s$, and $c_a$ according to a feasible flow solution (in terms of conservation and capacity constraints) which is not MCFP compliant (i.e., whose input data do not follow an optimal MCFP solution pattern). The second set of instances aims at observing how our model deals with data based on a wrong hypothesis (structure of an optimal solution of MCFP) and, hence, how the objective value is impacted. Moreover, we studied the impact of the quantity of known and unknown data by giving a fixed percentage of capacities for $\operatorname{MCFP}\left(\frac{\left|A^{\prime}\right|}{|A|} \times 100\right)$ as an input.

The resulting tables are organized as follows. The number of nodes $(|V|)$ and $\operatorname{arcs}(|A|)$ are reported in the caption of each table. The proportion of known capacities is specified in the first column “C(\%)”. The rest of the table is divided in 3 subsets of columns, 4 for each value of cardinality of $S$. The four columns report: (i) the amount of capacities “c(\%)” that has been successfully predicted (the percentage of successfully predicted capacities may be lower than the given ones due to the truncation process of “C(\%)|A’|”); (ii) the maximal absolute gap ( “Gap”) observed between the predicted capacities and the generated ones; (iii) the CPU time in seconds “T(s)” (we denote termination due to time limit by ${ }^*$ ); and (iv) objective value ” $\Delta “$.

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

For concepts and notations not defined here we refer the reader to [3]. All graphs that we consider here are simple (i.e., without loops or multiple edges). Let $G=(V, E)$ be a graph. If $u, v \in V$ and $u v \notin E, u v$ is called a nonedge of $G$. We write $G-v$ for the subgraph obtained by deleting vertex $v$ and all the edges incident to $v$. Similarly, we write $G-e$ for the subgraph obtained by deleting edge $e$ without deleting its endpoints.

Given a subset $A \subseteq V, G[A]$ stands for the subgraph of $G$ induced by $A$, and $G \backslash A$ denotes the induced subgraph $G[V \backslash A]$.

For each vertex $v$ of $G, N_G(v)$ denotes the neighbourhood of $v$ in $G$ and $N_G[v]$ denotes closed neighbourhood $N_G(v) \cup{v}$.

A clique is a set of pairwise adjacent vertices. A vertex $v$ is simplicial if $N_G(v)$ is a clique. A stable set is a set of vertices no two of which are adjacent. The complete graph on $n$ vertices corresponds to a clique on $n$ vertices and is denoted by $K_n . n K_1$ stands for a stable set on $n$ vertices. $K_4-c$ stands for the graph obtained from $K_4$ by deleting exactly one edge.

Given a graph $H$, we say that $G$ contains no induced $H$ if $G$ contains no induced subgraph isomorphic to $H$. If $\mathcal{H}$ is a family of graphs, a graph $G$ is said to be $\mathcal{H}$-free if $G$ contains no induced subgraph isomorphic to some graph belonging to $\mathcal{H}$.

Let $\mathcal{G}$ be a class of graphs. A graph belonging to $\mathcal{G}$ is called a $\mathcal{G}$-graph. If $G \in \mathcal{G}$ implies that every induced subgraph of $G$ is a $\mathcal{G}$-graph, $\mathcal{G}$ is said to be hereditary. If $\mathcal{G}$ is a hereditary class, a graph $H$ is a minimal forbidden induced subgraph of $\mathcal{G}$, or more briefly, minimally non- $\mathcal{G}$, if $H$ does not belong to $\mathcal{G}$ but every proper induced subgraph of $H$ is a $\mathcal{G}$-graph.

We denote as usual by $C_n, n \geq 3$, the chordless cycle on $n$ vertices and by $P_n$ the chordless path or induced path on $n$ vertices. A graph is called chordal if it does not contain any chordless cycle of length at least four. A block graph is a chordal graph which is $\left{K_4-e\right}$-free.

# 组合优化代考

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

myassignments-help数学代考价格说明

1、客户需提供物理代考的网址，相关账户，以及课程名称，Textbook等相关资料~客服会根据作业数量和持续时间给您定价~使收费透明，让您清楚的知道您的钱花在什么地方。

2、数学代写一般每篇报价约为600—1000rmb，费用根据持续时间、周作业量、成绩要求有所浮动(持续时间越长约便宜、周作业量越多约贵、成绩要求越高越贵)，报价后价格觉得合适，可以先付一周的款，我们帮你试做，满意后再继续，遇到Fail全额退款。

3、myassignments-help公司所有MATH作业代写服务支持付半款，全款，周付款，周付款一方面方便大家查阅自己的分数，一方面也方便大家资金周转，注意:每周固定周一时先预付下周的定金，不付定金不予继续做。物理代写一次性付清打9.5折。

Math作业代写、数学代写常见问题

myassignments-help擅长领域包含但不是全部: