Rob:
Thanks for offering to help.
The basic issue here is that this optimization problem is taking so long to solve that I keep getting unceremoniously kicked off of the SAS OnDemand for Academics server (a warning would be nice) for "excessive resource usage".
You helped me late last year with a similar problem by suggesting the invocation of the SYMMETRY option in Proc Optmodel. It helped speed the solution in that particular instance of the problem but, in this different instance, invoking the SYMMETRY option doesn't result in any orbits being found and appears to have no benefit.
Recently I came across a paper by Klotz and Newman entitled "Practical Guidelines for Solving Difficult Mixed Integer Linear Programs"--just what I need! In that paper they note that "lack of progress in the best integer solution" (which is what I seem to be experiencing) is best addressed by providing an initial solution. So that's what got me interested in using the PRIMALIN option and how I came to ask about the best approach to finding a Warm Start solution.
It puzzles me why this problem is so difficult to solve. In my uneducated opinion it seems to be a relatively straightforward (set cover or assignment?) problem: find the best orientation for 9 cameras that maximizes three-camera coverage over a set of Cartesian gridpoints. Each camera has only 16 possible orientations so there are only 9x16=144 possible solutions to choose from. How hard can that be?
I've prepared and attached the following the files:
1 Dataset (FoV.zip) that contains the field of view for each of 16 possible camera orientations. This is a zipped .csv file that will have to be un-zipped and imported into a SAS dataset.
2. Code (Data Preparation.sas) that invokes dataset (FoV) to prepare the "Region of Optimization Matrix" (RoO_Matrix) dataset. This is a 3 dimensional matrix of 9 stations (cameras), 16 orientations and several thousand targets (depending on the size of the Region of Optimization). Each element of the matrix is binary where k=1 when a target is covered by (i.e. within the field of view of) a given combination of camera and orientation or, otherwise, k=0.
Note: the path to dataset FoV needs to be specified in this Code at line 59.
3. The Optimization code (ProcOptodel.sas) consists of three parts:
Part 1 invokes Proc Optmodel, creates index sets for stations, orientation_string and targets, reads dataset RoO_Matrix, defines the model and solves it using MILP to provide the Warm Start solution by fixing the orientations of 4 stations based on my best guess. With RELOBJGAP=0.0, this problem solves in about 90 seconds.
Part 2 invokes Proc Optmodel using MILP with the PRIMALIN option to optimize all 9 stations. With RELOBJGAP=0.25 or lower the solution time exceeds 10 minutes, Best Integer progress is slows to a crawl and is at risk of getting a "Session terminated due to excessive resource usage" message when run on SAS OnDemand for Academics server.
Part 3. Produces a report and graphic output.
I would like for the code to solve without having to accept the sub-optimal solution that results when setting RELOBJGAP to a value that will stop the execution before the session is "terminated due to excessive resource usage".
Let me know if you have any questions or problems accessing the attached files.
Thanks so much for offering to help,
Gene
... View more
