Help Needed for Proc Optmodel

[genemroz]

I'm trying to replicate an Integer Linear Programming algorithm from the attached paper by Sadik et al. Specifically the formulation expressed on page 4 of that document. But I'm having a difficult time getting the equations encoded into Proc Optmodel. Below is the log output for the code as I've currently developed it. It's bleeding red with errors that reflect my ignorance. I'm hoping someone will more experience at this than I will help me get this code straightened out.

Specifically, it seems that the code as written has a problem with the variable XIT[target] that I don't understand. See log below.

Any help would be much appreciated.

Regards,

Gene

 
 1          OPTIONS NONOTES NOSTIMER NOSOURCE NOSYNTAXCHECK;
 72         
 73         
 74         Proc optmodel;
 75         /* Read CoverageMatrix data into index sets*/
 76         set <str> CAMERAS;
 77         read data optmodel.cameraorientations into CAMERAS=[station];
 NOTE: There were 22 observations read from the data set OPTMODEL.CAMERAORIENTATIONS.
 78         set <str> ORIENTATIONS=/'NHI' 'NLO' 'EHI' 'ELO' 'SHI' 'SLO' 'WHI' 'WLO'/;
 79         set <num> TARGETS;
 80         read data optmodel.targets into TARGETS=[target];
 NOTE: There were 49 observations read from the data set OPTMODEL.TARGETS.
 81         num Matrix {CAMERAS, ORIENTATIONS, TARGETS};
 82         read data optmodel.CoverageMatrix into [camera orientation target] Matrix=k;
 NOTE: There were 8624 observations read from the data set OPTMODEL.COVERAGEMATRIX.
 83         
 84         /* Set Constants*/
 85         
 86         %Let N=22; /*number of cameras*/
 87         num N=&N;
 88         
 89         
 90         /*Declare Variables*/
 91         /* Sadik Equation 11--Sets CHI as binary variable that is 1 when using CAMERA i and POSITION j else 0.*/
 92         
 93         var CHI {CAMERAS,ORIENTATIONS} binary;
 94         
 95         /*Sadik Equation 9 modified to maintain optimal coverage between 3 and 5 cameras*/
 96         
 97         var PSI{TARGETS} integer >=3 <=5;
 98         
 99         /* Declare Model*/
 100        
 101        /*Sadik Equation 7--the function to be maximized*/
 102        
 103        max OptCoverage=sum{target in TARGETS} Psi[target]
 104        -sum{camera in CAMERAS, orientation in ORIENTATIONS}Chi[camera,orientation];
 105        
 106        /*Subject to Following Constraints*/
 107        
 108        
 109        con CHI_constraint {orientation in ORIENTATIONS}:
 110        sum{camera in CAMERAS, orientation in ORIENTATIONS}CHI[camera,orientation] <=1;
                                    ___________
                                    708
 NOTE 708-782: The name 'orientation' hides an outer declaration.
 
 111        
 112        /* Sadik Equation 8*/
 113        
 114        /* Sadik: Syntax for expression XIT and  XIT_N for use in Sadik Equation 8 below*/
 115        
 116        var XIT{TARGETS} integer;
 117        
 118        
 119        XIT[target]=sum{camera in CAMERAS, orientation in ORIENTATIONS}
                 ______
                 525
 120        matrix[camera, orientation, target] * Chi[camera,orientation];
                                         ______
                                         525
 ERROR 525-782: The symbol 'target' is unknown.
 
 121        
 122        XIT_N[target]= XIT[target]/N;
             _____
             525
 ERROR 525-782: The symbol 'XIT_N' is unknown.
 
 122      ! XIT_N[target]= XIT[target]/N;
                   ______       ______
                   525          525
 ERROR 525-782: The symbol 'target' is unknown.
 
 123        
 124        con XIT_constraint{TARGETS}:XIT_N[target] <= PSI[target] <= XIT[target];
                                         _____
                                         525
 ERROR 525-782: The symbol 'XIT_N' is unknown.
 
 124      ! con XIT_constraint{TARGETS}:XIT_N[target] <= PSI[target] <= XIT[target];
                                               ______         ______         ______
                                               525            525            525
 ERROR 525-782: The symbol 'target' is unknown.
 
 125        
 126        /* Call Solver and Save Results*/
 127        
 128        solve;
 NOTE: Problem generation will use 2 threads.
 NOTE: Previous errors might cause the problem to be resolved incorrectly.
 ERROR: The constraint 'XIT_constraint' has an incomplete declaration.
 NOTE: The problem has 274 variables (49 free, 0 fixed).
 NOTE: The problem has 176 binary and 98 integer variables.
 NOTE: The problem has 8 linear constraints (8 LE, 0 EQ, 0 GE, 0 range).
 NOTE: The problem has 1408 linear constraint coefficients.
 NOTE: The problem has 0 nonlinear constraints (0 LE, 0 EQ, 0 GE, 0 range).
 NOTE: The OPTMODEL presolver is disabled for linear problems.
 NOTE: Unable to create problem instance due to previous errors.
 129        create data solution
 130        from [camera orientation target]={camera in matrix, orientation in matrix, target in matrix}: OptCoverage;
                                                         _______                _______           _______
                                                         615   515              615   515         615   515
                                                                                                         _
                                                                                                         22
                                                                                                         200
 ERROR 615-782: The name 'Matrix' is an array.
 
 ERROR 515-782: An indexing set subexpression may not be a number.
 
 ERROR 22-322: Syntax error, expecting one of the following: a name, ;, COL, {.  
 
 ERROR 200-322: The symbol is not recognized and will be ignored.
 
 131        quit;
 NOTE: The SAS System stopped processing this step because of errors.
 NOTE: PROCEDURE OPTMODEL used (Total process time):
       real time           0.06 seconds
       user cpu time       0.06 seconds
       system cpu time     0.01 seconds
       memory              4353.78k
       OS Memory           34780.00k
       Timestamp           03/26/2021 04:32:57 PM
       Step Count                        300  Switch Count  4
       Page Faults                       0
       Page Reclaims                     905
       Page Swaps                        0
       Voluntary Context Switches        52
       Involuntary Context Switches      0
       Block Input Operations            0
       Block Output Operations           16
       
 132        
 133        OPTIONS NONOTES NOSTIMER NOSOURCE NOSYNTAXCHECK;
 145        

[PinkOptimizer]

Hi there.

Your following constrain has "orientation" in both, the constraint definition as well as in the sum. It should be one of those.

 109        con CHI_constraint {orientation in ORIENTATIONS}:
 110        sum{camera in CAMERAS, orientation in ORIENTATIONS}CHI[camera,orientation] <=1;

The question to you is which of the following you need:

A. The sum of CHI over cameras to be  <= 1 for EACH orientation OR

B. The sum of CHI over cameras and orientations be <=1

Cheers,

Natalia

[genemroz]

Thanks, Natalia, for the prompt response.  Good catch on this constraint...

The answer to your question is that each camera can have only one orientation so I modified the code to eliminate summing over cameras but got the following error:

109        con CHI_constraint {orientation in ORIENTATIONS}:
 110        sum{orientation in ORIENTATIONS}CHI[camera,orientation] <=1;
                 ___________                     ______            _
                 708                             525               622
 NOTE 708-782: The name 'orientation' hides an outer declaration.
 
 ERROR 525-782: The symbol 'camera' is unknown.
 
 ERROR 622-782: Subscript 1 must be a string, found a number.

Did I do this correctly?

Thanks for taking a look at this,

Gene

[PinkOptimizer · Accepted solution]

Here is what you need:

con CHI_constraint {camera in CAMERAS}:
    sum{orientation in ORIENTATIONS} CHI[camera,orientation] <=1;

[PinkOptimizer]

On this issue:

 116        var XIT{TARGETS} integer;
 117        
 118        
 119        XIT[target]=sum{camera in CAMERAS, orientation in ORIENTATIONS}
                 ______
                 525
 120        matrix[camera, orientation, target] * Chi[camera,orientation];

You can re-write 119 and 120 as constraint:

con XIT_CON{target in TARGETS}:
   XIT[target]=sum{camera in CAMERAS, orientation in ORIENTATIONS}
               matrix[camera, orientation, target] * Chi[camera,orientation];

[genemroz]

Natalia,

I applied your suggested change and made a few additional ones of my own.  The error thrown by "create data solution" undoubtedly reflects the fact that I don't know how to create a data solution.  The desired output is a list of cameras with the optimal orientation.  Can you help with that? Below is the log from the code.

Thanks,

Gene

 
 1          OPTIONS NONOTES NOSTIMER NOSOURCE NOSYNTAXCHECK;
 72         
 73         
 74         Proc optmodel;
 75         /* Read CoverageMatrix data into index sets*/
 76         set <str> CAMERAS;
 77         read data optmodel.cameraorientations into CAMERAS=[station];
 NOTE: There were 22 observations read from the data set OPTMODEL.CAMERAORIENTATIONS.
 78         set <str> ORIENTATIONS=/'NHI' 'NLO' 'EHI' 'ELO' 'SHI' 'SLO' 'WHI' 'WLO'/;
 79         set <num> TARGETS;
 80         read data optmodel.targets into TARGETS=[target];
 NOTE: There were 49 observations read from the data set OPTMODEL.TARGETS.
 81         num Matrix {CAMERAS, ORIENTATIONS, TARGETS};
 82         read data optmodel.CoverageMatrix into [camera orientation target] Matrix=k;
 NOTE: There were 8624 observations read from the data set OPTMODEL.COVERAGEMATRIX.
 83         
 84         /* Set Constants*/
 85         
 86         %Let N=22; /*number of cameras*/
 87         num N=&N;
 88         
 89         
 90         /*Declare Variables*/
 91         /* Sadik Equation 11--Sets CHI as binary variable that is 1 when using CAMERA i and POSITION j else 0.*/
 92         
 93         var CHI {CAMERAS,ORIENTATIONS} binary;
 94         
 95         /*Sadik Equation 9 modified to maintain optimal coverage between 3 and 5 cameras*/
 96         
 97         var PSI{TARGETS} integer >=3 <=5;
 98         
 99         /* Declare Model*/
 100        
 101        /*Sadik Equation 7--the function to be maximized*/
 102        
 103        max OptCoverage=sum{target in TARGETS} Psi[target]
 104        -sum{camera in CAMERAS, orientation in ORIENTATIONS}Chi[camera,orientation];
 105        
 106        /*Subject to Following Constraints*/
 107        
 108        /*As corrected by Natalia*/
 109        con CHI_constraint {camera in CAMERAS}:
 110        sum{orientation in ORIENTATIONS}CHI[camera,orientation] <=1;
 111        
 112        /* Sadik Equation 8*/
 113        
 114        /* Sadik: Syntax for expression XIT and  XIT_N for use in Sadik Equation 8 below*/
 115        
 116        var XIT{TARGETS} integer;
 117        
 118        
 119        /*Natalia's suggestion*/
 120        con XIT_CON1{target in TARGETS}:
 121           XIT[target]=sum{camera in CAMERAS, orientation in ORIENTATIONS}
 122                       matrix[camera, orientation, target] * Chi[camera,orientation];
 123        
 124        /*What I had originally coded and replaced with Natalia's suggestion*/
 125        /*XIT[target]=sum{camera in CAMERAS, orientation in ORIENTATIONS}
 126        matrix[camera, orientation, target] * Chi[camera,orientation];*/
 127        
 128        
 129        /*XIT_N[target]= XIT[target]/N;*/
 130        
 131        con XIT_CON2{target in TARGETS}:XIT[target]/N <= PSI[target];
 132        
 133        
 134        /* Call Solver and Save Results*/
 135        
 136        solve;
 NOTE: Problem generation will use 2 threads.
 NOTE: The problem has 274 variables (49 free, 0 fixed).
 NOTE: The problem has 176 binary and 98 integer variables.
 NOTE: The problem has 120 linear constraints (71 LE, 49 EQ, 0 GE, 0 range).
 NOTE: The problem has 626 linear constraint coefficients.
 NOTE: The problem has 0 nonlinear constraints (0 LE, 0 EQ, 0 GE, 0 range).
 NOTE: The OPTMODEL presolver is disabled for linear problems.
 NOTE: The initial MILP heuristics are applied.
 NOTE: Optimal.
 NOTE: Objective = 245.
 137        create data solution
 138        from [camera orientation target]={camera in CAMERAS, orientation in ORIENTATIONS, target in TARGETS}:
                                                                                                                 _
                                                                                                                 22
                                                                                                                 200
 139        OptCoverage[camera,orientation,target];
                                                  _
                                                  616
 ERROR 22-322: Syntax error, expecting one of the following: a name, ;, COL, {.  
 
 ERROR 200-322: The symbol is not recognized and will be ignored.
 
 ERROR 616-782: The name 'OptCoverage' must be an array.
 
 140        quit;
 NOTE: The SAS System stopped processing this step because of errors.
 NOTE: PROCEDURE OPTMODEL used (Total process time):
       real time           0.09 seconds
       user cpu time       0.10 seconds
       system cpu time     0.00 seconds
       memory              24099.43k
       OS Memory           53792.00k
       Timestamp           03/26/2021 07:02:18 PM
       Step Count                        102  Switch Count  6
       Page Faults                       0
       Page Reclaims                     1484
       Page Swaps                        0
       Voluntary Context Switches        77
       Involuntary Context Switches      0
       Block Input Operations            0
       Block Output Operations           16
       
 141        
 142        OPTIONS NONOTES NOSTIMER NOSOURCE NOSYNTAXCHECK;
 154        

[PinkOptimizer]

Hi Gene, remove the “:”

[PinkOptimizer]

Actually, one more thing. If you only want to create a dataset with OptCoverage, which is not indexed on any set, you should do:

create data solution from OptCoverage;

[genemroz]

Natalia.

I ran the code as you suggested using:

create data solution from OptCoverage;

The code completed successfully, but the result, as can be seen in the log file below, only yields the Objective value (245).  I don't know how to code it to produce a list of the optimal orientation found for each camera?

Thanks for all your help,

Gene

 
 1          OPTIONS NONOTES NOSTIMER NOSOURCE NOSYNTAXCHECK;
 72         
 73         
 74         Proc optmodel;
 75         /* Read CoverageMatrix data into index sets*/
 76         set <str> CAMERAS;
 77         read data optmodel.cameraorientations into CAMERAS=[station];
 NOTE: There were 22 observations read from the data set OPTMODEL.CAMERAORIENTATIONS.
 78         set <str> ORIENTATIONS=/'NHI' 'NLO' 'EHI' 'ELO' 'SHI' 'SLO' 'WHI' 'WLO'/;
 79         set <num> TARGETS;
 80         read data optmodel.targets into TARGETS=[target];
 NOTE: There were 49 observations read from the data set OPTMODEL.TARGETS.
 81         num Matrix {CAMERAS, ORIENTATIONS, TARGETS};
 82         read data optmodel.CoverageMatrix into [camera orientation target] Matrix=k;
 NOTE: There were 8624 observations read from the data set OPTMODEL.COVERAGEMATRIX.
 83         
 84         /* Set Constants*/
 85         
 86         %Let N=22; /*number of cameras*/
 87         num N=&N;
 88         
 89         
 90         /*Declare Variables*/
 91         /* Sadik Equation 11--Sets CHI as binary variable that is 1 when using CAMERA i and POSITION j else 0.*/
 92         
 93         var CHI {CAMERAS,ORIENTATIONS} binary;
 94         
 95         /*Sadik Equation 9 modified to maintain optimal coverage between 3 and 5 cameras*/
 96         
 97         var PSI{TARGETS} integer >=3 <=5;
 98         
 99         /* Declare Model*/
 100        
 101        /*Sadik Equation 7--the function to be maximized*/
 102        
 103        max OptCoverage=sum{target in TARGETS} Psi[target]
 104        -sum{camera in CAMERAS, orientation in ORIENTATIONS}Chi[camera,orientation];
 105        
 106        /*Subject to Following Constraints*/
 107        
 108        /*As corrected by Natalia*/
 109        con CHI_constraint {camera in CAMERAS}:
 110        sum{orientation in ORIENTATIONS}CHI[camera,orientation] <=1;
 111        
 112        /* Sadik Equation 8*/
 113        
 114        /* Sadik: Syntax for expression XIT and  XIT_N for use in Sadik Equation 8 below*/
 115        
 116        var XIT{TARGETS} integer;
 117        
 118        
 119        /*Natalia's suggestion*/
 120        con XIT_CON1{target in TARGETS}:
 121           XIT[target]=sum{camera in CAMERAS, orientation in ORIENTATIONS}
 122                       matrix[camera, orientation, target] * Chi[camera,orientation];
 123        
 124        /*What I had originally coded and replaced with Natalia's suggestion*/
 125        /*XIT[target]=sum{camera in CAMERAS, orientation in ORIENTATIONS}
 126        matrix[camera, orientation, target] * Chi[camera,orientation];*/
 127        
 128        
 129        /*XIT_N[target]= XIT[target]/N;*/
 130        
 131        con XIT_CON2{target in TARGETS}:XIT[target]/N <= PSI[target];
 132        
 133        
 134        /* Call Solver and Save Results*/
 135        
 136        solve;
 NOTE: Problem generation will use 2 threads.
 NOTE: The problem has 274 variables (49 free, 0 fixed).
 NOTE: The problem has 176 binary and 98 integer variables.
 NOTE: The problem has 120 linear constraints (71 LE, 49 EQ, 0 GE, 0 range).
 NOTE: The problem has 626 linear constraint coefficients.
 NOTE: The problem has 0 nonlinear constraints (0 LE, 0 EQ, 0 GE, 0 range).
 NOTE: The OPTMODEL presolver is disabled for linear problems.
 NOTE: The initial MILP heuristics are applied.
 NOTE: Optimal.
 NOTE: Objective = 245.
 137        create data solution
 138        from OptCoverage;
 NOTE: The data set WORK.SOLUTION has 1 observations and 1 variables.
 139        quit;
 NOTE: PROCEDURE OPTMODEL used (Total process time):
       real time           0.09 seconds
       user cpu time       0.09 seconds
       system cpu time     0.01 seconds
       memory              23940.53k
       OS Memory           54048.00k
       Timestamp           03/26/2021 09:38:47 PM
       Step Count                        126  Switch Count  8
       Page Faults                       0
       Page Reclaims                     1206
       Page Swaps                        0
       Voluntary Context Switches        85
       Involuntary Context Switches      0
       Block Input Operations            0
       Block Output Operations           280
       
 
 140        
 141        OPTIONS NONOTES NOSTIMER NOSOURCE NOSYNTAXCHECK;
 153        

[PinkOptimizer]

Got it. Then you need:

create data opt_solution from 
   [camera orientation]={CAMERAS ORIENTATIONS}
   CHI;

 And if you wanted only the binary vars that are 1, then you can do:

create data opt_solution from 
   [camera orientation]={c in CAMERAS, o in ORIENTATIONS: CHI[c,o]>0.5}
   CHI;

Cheers,

Natalia

[genemroz]

Thanks, Natalia, for the prompt reply and sticking with me through this.

I made your recommended changes.  The program ran without error but it's giving the wrong answer.

I was expecting (hoping) for something that looks like this:

Camera Orientation

US000A NHI

US000C SLO

.

.

.20 more similar.

Instead, I'm getting

Camera Orientation

US000A NHI

US000C NHI

20 more similar

US000A NLO

US000C NLO

20 more similar through to the 8th Orientation.

For a total of 176 output rows which is the product of 22 cameras by 8 possible orientations. The same output was generated by both 'create solution data from...' statements that you recommended.

So something is amiss in the logic structure of the program.  

I'll study it but right now I'm stumped.  Feel free to look over the logic structure for any mistakes that might catch your practiced eyes but would evade my inexperienced ones.

The log output is below

Thanks again for all your help,

Gene

Proc optmodel;
/* Read CoverageMatrix data into index sets*/
	set <str> CAMERAS;
	read data optmodel.cameraorientations into CAMERAS=[station];
	set <str> ORIENTATIONS=/'NHI' 'NLO' 'EHI' 'ELO' 'SHI' 'SLO' 'WHI' 'WLO'/;
	set <num> TARGETS;
	read data optmodel.targets into TARGETS=[target];
	num Matrix {CAMERAS, ORIENTATIONS, TARGETS};
	read data optmodel.CoverageMatrix into [camera orientation target] Matrix=k;
	
/* Set Constants*/
	
	%Let N=22; /*number of cameras*/
	num N=&N;
	

/*Declare Variables*/
	/* Sadik Equation 11--Sets CHI as binary variable that is 1 when using CAMERA i and POSITION j else 0.*/ 
 
	var CHI {CAMERAS,ORIENTATIONS} binary;

	/*Sadik Equation 9 modified to maintain optimal coverage between 3 and 5 cameras*/

	var PSI{TARGETS} integer >=3 <=5;

/* Declare Model*/

	/*Sadik Equation 7--the function to be maximized*/
	
	max OptCoverage=sum{target in TARGETS} Psi[target]
	-sum{camera in CAMERAS, orientation in ORIENTATIONS}Chi[camera,orientation];

/*Subject to Following Constraints*/

	/*As corrected by Natalia*/
	con CHI_constraint {camera in CAMERAS}: 
	sum{orientation in ORIENTATIONS}CHI[camera,orientation] <=1;

/* Sadik Equation 8*/

	/* Sadik: Syntax for expression XIT and  XIT_N for use in Sadik Equation 8 below*/
	
		var XIT{TARGETS} integer;
		
		
	/*Natalia's suggestion*/
	con XIT_CON1{target in TARGETS}:
   XIT[target]=sum{camera in CAMERAS, orientation in ORIENTATIONS}
               matrix[camera, orientation, target] * Chi[camera,orientation];
               
	/*What I had originally coded and replaced with Natalia's suggestion*/
	/*XIT[target]=sum{camera in CAMERAS, orientation in ORIENTATIONS}
	matrix[camera, orientation, target] * Chi[camera,orientation];*/
	
	
	/*XIT_N[target]= XIT[target]/N;*/

	con XIT_CON2{target in TARGETS}:XIT[target]/N <= PSI[target];
	

/* Call Solver and Save Results*/
/*Per Natalia's recommendation*/

	solve;
	create data solution1 from
	[camera orientation]={CAMERAS, ORIENTATIONS} CHI;
	create data solution2 from 
	[camera orientation]={c in cameras, o in orientations: CHI[c,o]<0.5} CHI;
	quit;

[RobPratt]

There are two issues:

1. You have reversed the > 0.5 to < 0.5, so in solution2 you are outputting the 0 variables instead of the 1 variables.
2. The constraints you have so far allow a trivially optimal solution with PSI[t] = 5 for all t and all other variables 0.

[genemroz]

Rob,

Thanks for the note.  Yes, I noticed the problem with the inequality sign reversal.  That fix rectified the problem. 

So with much gratitude to Natalia who patiently helped me de-bug my code, I have my optimization model operating.  I couldn't have done this without her help.  SAS Communities has been of great help to me as I struggle up the SAS learning curve.  Thanks again for all that Rob, Natalia and all the Advisers do to help users up the curve. 

So while I hereby close this thread, I fully expect to be back here in the future with yet another question.

Gratefully yours,

Gene

[PinkOptimizer]

Thanks for the sweet message Gene and glad we were helpful!

Cheers,

Natalia