topic Re: Integer quadratic solver in PROC OPTMODEL? in Mathematical Optimization, Discrete-Event Simulation, and OR

Integer quadratic solver in PROC OPTMODEL?

genemroz — Sun, 06 Jun 2021 17:17:54 GMT

I'm trying to implement an algorithm in Proc Optmodel that has a quadratic term and, I believe, requires the application of integer quadratic programming. Proc Optmodel produces an error message that the "QP solver does not allow integer variables. The LSO solver might be suitable for this problem". But when I attempt to solve with the LSO solver, I get an "out of memory" error message. The relevant code for Proc Optmodel is below. I would appreciate any guidance on this issue.

Thanks,

Gene

Proc optmodel;
/* Read CoverageMatrix data into index sets*/
	set <str> stations;
	read data socal.stationdataexisting  into stations=[station];
	set <str> ORIENTATIONS=/'NOHI' 'NOMD' 'NOLO' 
	'NEHI' 'NEMD' 'NELO' 
	'SEHI' 'SEMD' 'SELO' 
	'SOHI' 'SOMD' 'SOLO' 
	'SWHI' 'SWMD' 'SWLO' 
	'NWHI' 'NWMD' 'NWLO'/;
	set <num> TARGETS;
	read data work.targets into TARGETS=[target];
	num Matrix {stations, ORIENTATIONS, TARGETS};
	read data work.CoverageMatrixOpt into [station orientation target] Matrix=k;
	
/* Set Constants*/
	
	%Let N=3; /*number of stations*/
	num N=&N;
	

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

	/*Sadik Equation 9.*/

	var PSI{TARGETS} integer <=3;

/* Declare Model*/

	/*Sadik Equation 7--the function to be minimized where 3 is constant k (max value of variable PSI{TARGETS}*/
	
	minimize OptCoverage=sum{target in TARGETS} (3-Psi[target])**2
	-sum{station in stations, orientation in ORIENTATIONS}Chi[station,orientation];

/*Subject to Following Constraints*/

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

/* Sadik Equation 8*/
	
		var XIT{TARGETS} integer;
		
	con XIT_CON1{target in TARGETS}:
   XIT[target]=sum{station in stations, orientation in ORIENTATIONS}
               matrix[station, orientation, target] * Chi[station,orientation];
	
	
	/*XIT_N[target]= XIT[target]/N;*/

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

/* Call Solver and Save Results*/
	solve;

Re: Integer quadratic solver in PROC OPTMODEL?

RobPratt — Sun, 06 Jun 2021 18:13:01 GMT

Can you please also provide the input data sets?

Re: Integer quadratic solver in PROC OPTMODEL?

genemroz — Sun, 06 Jun 2021 19:48:37 GMT

Rob,

Thanks for your prompt response.

I don't know the preferred way for posters like myself to send large datasets in support of questions like the one I posted today. I started to winnow down the size of the dataset in the hope of finding a more manageable size and discovered that the LSO Solver would run on a smaller subset without an "out of memory" error so obviously problem #1 is that the dataset is too large for SAS OnDemad for Academics. But the LSO Solver also reported the "best solution found does not satisfy the feasibility tolerance". Not exactly sure what that means but it appears to suggest I'm heading down a dark alley to a dead end anyway. So I'll terminate this thread for now until I can come up with a better posed question. And I thank you again for your generous offer to help.

Regards,

Gene

Re: Integer quadratic solver in PROC OPTMODEL?

RobPratt — Sun, 06 Jun 2021 20:03:02 GMT

Here's an approach that linearizes the quadratic objective so that you can use the MILP solver:

   num k = 3;
   var Psi {TARGETS} integer <= k;
   set VALUES = 0..k;
   var IsValue {TARGETS, VALUES} binary;
   con OneValue {t in TARGETS}:
      sum {v in VALUES} IsValue[t,v] = 1;
   con LinkIsValuePsi {t in TARGETS}:
      sum {v in VALUES} v*IsValue[t,v] = Psi[t];
   minimize OptCoverage = sum{t in TARGETS, v in VALUES} (k-v)^2 * IsValue[t,v]
	-sum{station in STATIONS, orientation in ORIENTATIONS} Chi[station,orientation];

Re: Integer quadratic solver in PROC OPTMODEL?

genemroz — Sun, 06 Jun 2021 20:13:14 GMT

Thanks, Rob. I'll try your suggestion.

Gene