Problem with mathematical formulation
Awaiting user inputHello everyone,
I am trying to formulate the following problem.
Imagine I have a set of undrawn circles,. My goal is to try to draw the red or blue circle in such a way that there is always a sequence red circle-blue circle-red circle-blue circle-... so on between all the circles I have, and in this way minimize the amount of red circles.
I would appreciate your help.
-
Official comment
-
Gurobi Staff
This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum, or try Gurobot, our chatbot interface offering instant, expert-level support. -
-
-
Hi JC,
Sorry, but it is impossible for me to understand the actual optimization problem. Could you please be a bit more detailed, probably by providing a formal problem description?
Best regards,
Mario0 -
-
Sorry Mario,
Thank you very much for your response and sorry for not being clear.
The problem is the following: I am using Gurobi as a solver and I have the problem of minimizing the amount of red circles to be distributed in a network like the one in the attached figure. I mean I can draw the circles with red or blue colour, my goal is to minimise the amount of red circles and basically my only restriction would be that I must be able to have always alternation between red and blue circles between any two circles of my grid.
As you can see on the right of the figure, any pair of circles that I take for example between 1 and 3 (blue-red-blue), or between 2 and 5 (red-blue-red) or even between 1 and 5 (blue-red-blue-red) will always alternate colours.
Thank you in advance
0 -
-
How could I do the mathematical formulation of this problem or where to look to have a day of how to solve it ?
0 -
-
Sorry, not day is idea
0 -
-
-
Hi JC,
Ok, now I got it. This might be related to the graph-theoretical concept of an independent (or stable) set.
The term "circle" puzzled me, actually you mean a vertex or a node in a graph. You might define a binary variable r_i for each node i that denotes whether the color is red or not. As objective you minimize the sum over all those variables. As constraints, for each connection in the graph one of the two endpoints has to be red, right? So, for each connection (i,j), r_i + r_j = 1 must hold. I think, that's it.
Why do you need to solve that problem? Is this some kind of exercise you need to do in your studies? If yes, tell me which grade I got :)
Best regards,
Mario0 -
-
Hello Mario,
Thank you very much for your reply. No, don't worry, it's not a school exercise. I am learning a bit of Gurobi to maybe apply it in some research.
Indeed, the circles are nodes, I called it that way to make it more generic. The solution you give me does not scale (I had already thought about it :) , I also try to do it with two decision variables) because when the number of nodes increases in a full-mesh topology the constraints do not allow you to reach a feasible solution.
The problem is simple apparently, we will have to keep on working ...
Best regards,
JC0 -
-
-
Hi JC,
In which sense does it not scale? Is the runtime not reasonable anymore for larger instances?
Of course, if you have cycles of odd length in your graph, then the problem is infeasible. But you might be able to detect this a priori with a dedicated algorithm (based on depth-first search).
Best regards,
Mario0 -
-
Hello Mario,
Yes when I have cycles of odd length is not feasible the solution.
So my case is that I have a network , of it I know its vertices and edges (directed graph) and let's say a dictionary of requests R , such that I have requests between every pair of nodes in the network. With the flow conservations constraints I guarantee the shortest path between the nodes that compose R ... the problem comes now --->>> the vertices that form the path between two nodes have to alternate colour in such a way that the sum of the red vertices for all R has to be minimal.
That is one of my problems. My other problem is that I don't know in which book to read or search, I have searched a lot but I only get basic examples but none with anything like "constraints on/with flow conservation". Can you recommend me some solution ?
Thank you very much in advance.
0 -
-
-
Hi JC,
Is the coloring of nodes for one particular request independent of the other requests? Or is a "red" node red for all requests? If only the chosen path for each request needs to be alternating in color, then there could be two neighboring red nodes in a solution, as long as the edge in-between is not used in any path. Is that true?
I do not know a particular book where such a problem is described but the problem might be related to telecommunications applications, or network design with relays.
Best regards,
Mario0 -
Post is closed for comments.
Comments
10 comments