private static void extendNetwork() {
		
		int n = network.getNumberOfVertices();
		
		// Compute M
		long bigM = 1;
		long maxCost = 0;
		for (Edge edge : network.getEdges()) {
			NetworkEdge e = (NetworkEdge) edge;
			long cost = Math.abs(e.getCost());
			if (maxCost < cost) {
				maxCost = cost;
			}
		}
		bigM = 1 + Math.round(0.5*n*maxCost);
		
		// Add a new vertex k to the network
		root = new NetworkVertex();
		root.setName("0");
		root.setDemand(0L);
		network.addVertex(root, 0); // we give k the id 0
		n = n+1;
		for (Vertex vertex : network.getVertices()) {
			NetworkVertex v = (NetworkVertex) vertex;
			if (v != root) {
				// Compute net demand (Nettobedarf: Mindestlieferung - Mindestbedarf)
				// b'(v) = b(v) - l(delta_p(v)) + l(delta_m(v))
				// delta_p(v) := {outgoing edges of v}
				// delta_m(v) := {ingoing edges of v}
				long b = v.getDemand();
				long nb = b;
				for (Edge edge : v.getOutgoingEdges()) {
					NetworkEdge e = (NetworkEdge) edge;
					nb -= e.getLowerBound();
				}
				for (Edge edge : v.getIngoingEdges()) {
					NetworkEdge e = (NetworkEdge) edge;
					nb += e.getLowerBound();
				}
				// Depends on the net demand,
				// add a new edge (v,k) or (k,v) to the network
				NetworkEdge e;
				if (nb > 0) {
					e = new NetworkEdge(v,root);
				} else {
					e = new NetworkEdge(root,v);
				}
				e.setLowerBound(0L);
				e.setCapacity(Long.MAX_VALUE);
				e.setCost(bigM);
				network.addEdge(e);
			}
		}
	}