How can we formulate the art gallery problem as a mixed-integer linear program?

155 Views Asked by At

Specifically, how would one go about using 'intlinprog' in MATLAB to get a minimum value for the cameras required in a polygon-shaped art gallery? In other words, I think that what I am looking for is how to represent the art gallery problem mathematically.

The art-gallery problem is to minimize the number of cameras that you need to have, in order to secure a polygon-shaped art-gallery. We can triangulate the polygon and have a camera in each triangle (on one of the verteces of the triangle). Also, note that we can express the triangulation of the polygon as a matrix. My problem is that I cannot figure out what I should put as the parameters in the intlinprog command, which is as following: intilinprog(f,intcon,A,b,Aeq,beq,lb,ub).

Here is the help from MATLAB for the command: http://www.mathworks.com/help/optim/ug/intlinprog.html