Gurobi Python - Add certain vars - gurobi

I'm new to Gurobi and I'd like to know how to add certain variables to a model. For example, if I have an uncomplete graph, I'd like to add a variable x[i,j] for each arc of the graph. I don't want to add all the arcs of the complete graph, because it has a huge number of nodes and my computer runs out of memory. So I'm trying to avoid defining variables with lists for it's indexes.
Thanks in advance,

I think that you know arcs that you want to add. If it is that, you can define a set (list ou dict) of arcs like Arcs={(i,j): value of arc (i,j)}. This set concern only arcs that you want to add.

This is illustrated in the netflow.py example, which can be found in the examples\python subdirectory.

Related

How to create an x=y-axis

I have this wave in Maple, but I don't want to have the whole square showing, I just want one of the triangular parts visible. Hope that makes sense. Basically I need to axis to go from say x=0..1, y=0..1 and x=y. It is this x=y axis which I can't get.
This is the code which I have so far.
with(plots):
animate(plot3d,[sin(Pi*2*x)*sin(Pi*y)*sin(t)-sin(Pi*x)*sin(Pi*2*y)*sin(t),x=0..1, y=0..1],t=0..2*Pi);
The plot3d command offers a syntax where either (or both) of the endpoints in the range supplied for one of the plotting variables can be an expression in terms of the other plotting variable.
So instead of x=0..1, y=0..1 to denote a rectangular domain you could use x=0..y, y=0..1 to denote a triangular domain. The remaining triangular domain could be denoted using x=y..1, y=0..1.
You utilized this functionality in another of your recent questions.
with(plots):
animate(plot3d,[sin(Pi*2*x)*sin(Pi*y)*sin(t)
-sin(Pi*x)*sin(Pi*2*y)*sin(t),
x=0..y, y=0..1],
t=0..2*Pi);
And the remaining portion could be had by,
animate(plot3d,[sin(Pi*2*x)*sin(Pi*y)*sin(t)
-sin(Pi*x)*sin(Pi*2*y)*sin(t),
x=y..1, y=0..1],
t=0..2*Pi);

Object and Pointer Graph representations

I keep seeing everywhere that there are 3 ways to represent graphs:
Objects and pointers
Adjacency matrix
Adjacency lists
However, I just plain don't understand what these Object and pointer representations are - yet every recruiter, and many blogs cite Steve Yegge's blog that they are indeed a separate representation.
This widely accepted answer to a very similar question seems to suggest that the vertex structures themselves have no internal pointers to other vertices, and instead all edges are represented by edge structures which contain pointers to the adjacent vertices.
How does this representation offer any discernible analytical advantage in any scenario?
From the top of my head, I hope I have the facts correct.
Conceptually, graph tries to represent how a set of nodes (or vertices) are related (connected) to each other (via edges).
However, in actual physical device (memory), we have a continuous array of memory cell.
So, in order to represent the graph, we can choose to use a matrix.
In this case, we use the vertex index as the row and column and the entry has value 1 if the vertices are adjacent to each other, 0 otherwise.
Alternatively, you can also represent a graph by allocating an object to represent the node/vertex which points to a list of all the nodes that are adjacent to it.
The matrix representation gives the advantage when the graph is dense, meaning when most of the nodes/vertices are connected to each other. This is because in such cases, by using the entry of matrix, it saves us from having to allocate an extra pointer (which need a word size memory) for each connection.
For sparse graph, the list approach is better because you don't need to account for the 0 entries when there is no connection between the vertices.
Hope it helps.
For now I have a hard time finding a pro w.r.t typical "graph algorithms". But it sure is possible to represent a graph with objects and pointers and a very natural thing to do if you think of it as a representation of something you just drew on a whiteboard.
Think of a scenario where you want to combine nodes of a graph in a certain order.
Nodes have payloads that contain domain data, the graph structure itself is not a core aspect of your program.
Sure, you can update your lists / matrix for every operation, but given an "objects and pointers" structure, you can do the merging locally. Further, if nodes have payloads, it means that lists/matrix will feature node id's that identify the actual node objects. A combination would mean you update your graph representation, follow the node identifiers and do the actual processing. It may feel more intuitively to work on your actual node objects and simply remove pointerswhen collapsing a neighbor (and delete that node) .
Besides, there are more ways to represent a graph:
E.g. just as triples, like Turle does
Or as offset
representation (offsets per node into an edge array), e.g. this
Boost data structure (disclaimer: I have not tested the linked
implementation myself)
etc
Here a way i have been using to create Graph with this concept :
#include <vector>
class Node
{
public:
Node();
void setLink(Node *n); // *n as argument to pass the address of the node
virtual ~Node(void);
private:
vector<Node*> m_links;
};
And the function responsible for creating the link between vertices is :
void Node::setLink(Node *n)
{
m_links.push_back(n);
}

Grab objects near camera

I was looking at the http://threejs.org/examples/webgl_nearestneighbour.html and had a few questions come up. I see that they use the kdtree to stick all the particles positions and then have a function to determine the nearest particle and color it. Let's say that you have a canvas with around 100 buffered geometries with around 72000 vertices / geometry. The only way I know to do this is that you get the positions of the buffered geometries and then put them into the kdtree to determine the nearest vertice and go from there. This sounds very expensive.
What other way is there to return the objects that are near the camera. Something like how THREE.LOD does it? http://threejs.org/examples/#webgl_lod It has the ability to see how far an object is and render the different levels depending on the setting you inputted.
Define "expensive". The point of the kdtree is to find nearest neighbour elements quickly, its primary focus is not on saving memory (Although it does everything inplace on a typed array, it's quit cheap in terms of memory already). If you need to save memory you maybe have to find another way.
Yet a typed array with length 21'600'000 is indeed a bit long. I highly doubt you have to have every single vertex in there. Why not have a position reference point for every geometry part? And, if you need to get the vertices associated to that point, a dictionary. Then you can call myGeometryVertices[ geometryReferencePoint ].
Three.LOD works with raycasts. If you have a (few) hundred objects that might work well. If you have hundred thousands or even millions of positions you'll get some troubles. Also if you're not using meshes; you can't raytrace e.g. a particle.
Really just build your own logic with them. None of those two provide a prebuilt perfect-for-all-cases solution.

What is BufferedGeometry

Could someone please explain to me what BufferedGeometry is in the context of three? How is it different from normal geometry. Arn't they making the same calls to the graphics card? Also, would using BufferedGeometry be a speed improvement when making a terrain solution. At the moment I have created a terrain solution that uses hundreds of little meshes placed next to each other. This method was a slight improvement in speed compared with using a single PlaneGeometry object (presumably because mip mapping and culling can be applied more readily). However its still not great and the performance gets jerky on big landscapes - I was wondering if I should pursue BufferedGeometry or just accept the solution I have right now and limit it to small maps?
Thanks :)
Buffered geometry is a different way of sending data down to the gpu. Yes it is a speed improvement so you can give it a try.
Geometry looks something like this
class Geometry {
this.vertices = []; //javascript array
this.faces = []; //another javascript array
this.uvs = [];
...
}
its just a JS class
these arrays contain some complicated stuff, other classes and structures.
this.vertices[0] will be a THREE.Vector3 which is another class - has data and methods, but the data is just three floats, so its pretty simple. Could have been an array [x,y,z] instead of an object with members, but then you wouldn't have the methods along with it.
this.faces[0] is more complicated. It holds indecis into vertices, which makes a triangle (a,b,c), but it also can hold stuff like face normal (another vec3), a tangent, a binormal, per face color etc etc.
In three, this is also where vertexNormals are stored.
WebGL has no idea how to interpret any of this stuff. It understand typedArrays, so in order to even start working with Geometry on the GPU it needs to be converted to a WebGL friendly format.
This is what BufferGeometry is. It's the same data, organized in a different way that is more low-level gpu friendly.
There are no javascript classes, no methods, no references. You have to be aware of how these arrays are filled and manage offsets and sizes.
Three JS objects THREE.Vector3 turn into one Float32Array(9) [xyzxyzxyz].
Face doesn't have room to store all that stuff, it's just another order in another array:
Uint16Array(3) [0,1,2] (meaning: make a triangle out of vertices 0 , 1 and 2, meaning, look up into that vertex array at offsets 0 * 3 , 1 * 3 and 2 * 3.
This is the jist of it. Faster, less memory, less flexible.
If you are going to manipulate your terrain with shaders, you should use bufferGeometry. If you want to do lookups like "find nearest neighbor to this triangle, or this vertex" you are most likely going to need structure, so you either build something yourself or use Geometry.

What are good ways of organizing directed graph data?

Here's my situation. I have a graph that has different sets of data being added at different times. For example, set1 might have a few thousand nodes and then set2 comes in later and we apply business logic to create edges from set1 to set2(and disgard any Vertices from set1 that do not have edges to set2). Then at a later point, we get set3, set4, and so on and the same process applies between each set and its previous set.
Question, what's the best way to organize this? What I did before was name the nodes set1-xx, set2-xx,etc.. The problem I faced was when I was trying to run analytics between the current set and the previous set I would have to run a loop through the entire graph and look for all the nodes that started with 'setx'. It took a long time as the graph grew, so I thought of another solution which was to create a node called 'set1' and have it connected to all nodes for that particular set. I am testing it but I was wondering if there way a more efficient way or a build in way of handling data structures like this? Is there a way to somehow segment data like this?
I think a general solution would be application but if it helps I'm using neo4j(so any specific solution to that database would be good as well).
You have a very special type of a directed graph, called a layered graph.
The choice of the data structure depends primarily on the expected graph density (how many nodes from a previous set/layer are typically connected to a node in the current set/layer) and on the operations that you need to perform on it most of the time. It is definitely a good idea to have each layer directly represented by a numeric index (that is, the outermost structure will be an array of sets/layers), and presumably you can also use one array of vertices per layer. However, the list of edges per vertex (out only, or in and out sets of edges depending on whether you ever traverse the layers backward) may be any of the following:
Linked list of vertex identifiers; this is good if the graph is very sparse and edges are often added/removed.
Sorted array of vertex identifiers; this is good if the graph is quite sparse and immutable.
Array of booleans, indexed by vertex identifiers, determining whether a given vertex is or is not linked by an edge from the current vertex; this is good if the graph is dense.
The "vertex identifier" can take many forms. For example, it can be an index into the array of vertices on the next layer.
Your second solution is what I would do- create a setX node and connect all nodes belonging to that set to setX. That way your data is partitioned and it is easier to query.

Resources