topic Re: binary variables with price in objective function in Mathematical Optimization, Discrete-Event Simulation, and OR

binary variables with price in objective function

Luengjiranothai — Fri, 25 Jul 2014 06:27:20 GMT

I use binary variables with price that enters into the objective function.
The result does not seem to be correct that these prices be evaluated for binary variables.

I write it first in sparsedata and convert into MPS with PROC LP and run in with OPTMILP.

Can you tell about binary variables that, whether it be considered in objective function?

Re: binary variables with price in objective function

RobPratt — Fri, 25 Jul 2014 14:49:01 GMT

Yes, binary variables are supported in the objective function for the MILP solver.

Can you please share your code, sparsedata data set, or MPS data set? By the way, OPTMODEL is the recommended procedure for formulating and solving mathematical optimization problems.

Re: binary variables with price in objective function

Luengjiranothai — Mon, 28 Jul 2014 07:57:34 GMT

We unfortunately can not use OPTMODEL because of dependency of software we implemented.

We run MILP use sasmacro:

PROC OPTMILP

DATA=MPSMODEL

PRIMALOUT=PrimalSolution

DUALOUT=DualSolution

PRINTLEVEL=2

PRINTLEVEL2=MODERATE

PRESOLVER=MODERATE

MAXTIME=300;

run;

Please find attached the MPS data set file.

Thank you very much

Re: binary variables with price in objective function

user24feb — Tue, 29 Jul 2014 09:27:23 GMT

Do you mind posting the sparse data as well (%sasmpsxs doesn't work)?

Re: binary variables with price in objective function

Luengjiranothai — Tue, 29 Jul 2014 10:01:19 GMT

Hello user24feb, sure but I first need to know, why you need the sparse data?

Re: binary variables with price in objective function

RobPratt — Tue, 29 Jul 2014 18:58:21 GMT

This seems to solve fine in SAS/OR 13.1 (the latest production release, from December 2013). The binary variables take integer values in the resulting solution, and summing up the _OBJCOEF_ * _VALUE_ from the PrimalSolution data set yields the same objective value that is shown in the log. What behavior are you seeing instead?

NOTE: The problem PROBLEM has 8042 variables (2555 binary, 0 integer, 0 free, 0 fixed).

NOTE: The problem has 3686 constraints (2202 LE, 1472 EQ, 12 GE, 0 range).

NOTE: The problem has 17188 constraint coefficients.

NOTE: The MILP presolver value MODERATE is applied.

NOTE: The MILP presolver removed 0 variables and 24 constraints.

NOTE: The MILP presolver removed 24 constraint coefficients.

NOTE: The MILP presolver modified 0 constraint coefficients.

NOTE: The presolved problem has 8042 variables, 3662 constraints, and 17164 constraint

coefficients.

NOTE: The MILP solver is called.

Node Active Sols BestInteger BestBound Gap Time

0 1 0 . 303907325 . 0

NOTE: The MILP solver added 1 cuts with 3 cut coefficients at the root.

27 10 2 6096111710 303907326 1905.91% 4

52 23 3 5570543121 303907327 1732.97% 5

100 25 3 5570543121 303907327 1732.97% 5

200 53 3 5570543121 303907327 1732.97% 6

220 59 4 303907696 303907327 0.00% 7

NOTE: Optimal within relative gap.

NOTE: Objective = 303907695.65.

NOTE: The data set WORK.PRIMALSOLUTION has 8042 observations and 8 variables.

NOTE: The data set WORK.DUALSOLUTION has 3686 observations and 8 variables.

NOTE: PROCEDURE OPTMILP used (Total process time):

real time 30.95 seconds

cpu time 7.48 seconds

Re: binary variables with price in objective function

Luengjiranothai — Wed, 30 Jul 2014 07:50:18 GMT

The result that we get not provide optimal objective function. Most binary variables takes the value of 1, even though they can take the value 0, and instead the cheaper binary variables could take the value 1 in the same equation.

If you understand the problem and the modeling behind. And I you have the GUI that the result presents in the way in use, it will be immediately apparent.

We are currently using SAS 9.2.

With parameter RELOBJGAP = 1e-9 it delivered better value for some binary variables, but not all (Time limit reached).
Increase time limit (1 hour) yielded SAS "OUT OF MEMORY".

Re: binary variables with price in objective function

Philipp_SAS — Wed, 30 Jul 2014 14:32:23 GMT

It seems to me that your way to model the problem requires a strictly optimal solution, meaning the optimality gap has to be closed completely. By default, MILP solvers use a relative objective gap to stop early when the primal and dual bound are close to each other in a relative sense. Since the objective value for this problem is so big and the objective coefficients for the binary variables in question are so small, there exist better solutions between the default primal solution returned and the dual (optimality) bound.

Tightening RELOBJGAP= will force the solver to go on to find better solutions. Of course it gets harder for the solver to proof optimality for numerical reasons and a newer version of the MILP solver will do a better job. The best solution I was able to find with some quick tests I ran (on the latest solver version) had an objective value of 303907434 and is at most 103 away from the true optimal value as far as I know. I attached this solution to this post. Does that give you the result you expect? You can use the PRIMALIN= option to read it into your OPTMILP run as an input solution.

Re: binary variables with price in objective function

Luengjiranothai — Wed, 30 Jul 2014 15:24:01 GMT

I can not open the file you attached. It say the version of sas is inkompatible, but thank you.

I think it solves our problem is not to find the best values for this problem. The model represents only an example of the problem. There may be much larger and much more binary variables.

However, for our application is important to get all binary variables always optimal value, otherwise we can not prove the correctness of the solution to the problem. And if the solver has difficulty to deliver the optimal binary variables, then we can not use this modeling.

Maybe there are better modeling, but I have no idea