Re: selecting subset of table parameter values based on variable values
Paul
If you want to stick to the math programming paradigm, the only way I know to use a variable as a vector/matrix/table index involves binary variables.
Paul
Robert Fourer
I think you have to accept that if you write your model in the most mathematically concise way, then it will not be linear. If you want to make it linear, you'll have to do some reformulation. You could use the general approach of defining zero-one variables Z[c] so that the following hold (where the sums are over the domain of c):
The sum of the Z[c] equals 1.
The decision variable equals the sum of possible-value[c] * Z[c].
The table value is given by the sum of Table[a,b,c] * Z[c].
If there's actually an indexed collection of decision variables then the same indexing will have to be added to Z as well, so that there's a different series of zero-one variables for each original decision variable.
Some alternative solvers can deal with formulations where there is an integer-valued variable subscripting a parameter, but this kind of expression is not as yet supported by AMPL. Also the functions floor and ceil, applied to variables, create discontinuous functions that present great difficulties for solving directly, and so it is best to look for ways of working around them.
Bob Fourer
From: am...@googlegroups.com [mailto:am...@googlegroups.com]
On Behalf Of bethanyc
Sent: Friday, February 08, 2013 7:29 PM
To: am...@googlegroups.com
Subject: [AMPL 6597] selecting subset of table parameter values based on variable values
I have a follow-up question to my earlier post about sorting variables (https://groups.google.com/d/topic/ampl/WeDmSeY1eWg/discussion). I mentioned how I wanted to create lookup tables to feed into my model (more specifically, these tables would contain breakpoint and slope values for a linear piecewise formulation). Instead of using variables to create these lookup tables (as I was trying to do before), I am now using parameter values that I feed in. Each table is a 2D slice of a 3D overall parameter (e.g., Table[a,b,c], where I iterate my 2D .dat files, let's say, over the b index). The rows (index a) contain the breakpoint and slope values for a single linear piecewise formulation. The columns (index c) represent different linear piecewise "fits," which correspond to the range of possible outcomes of a decision variable, where the decision variable value would fall into one of these pre-defined column "bins." That is, whichever column the decision variable best matches, I want the model to ONLY use that column (index c in this case) of linear piecewise beakpoint and slope values for that particular table slice (index b).
The problem, of course, is that you cannot use variables in the indexing of a parameter. So I can't just say Table[a,b,"decision variable"]. Plus, in my case, the decision variable has to first be manipulated to match the possible values of c (right now they are 0.1, 0.2, .... , 1.0), and I thought using ceil or floor would make it nonlinear (although I did try this and did not get any errors about non-linearity...). So....my questions are:
1) Is there some way to (simply) determine which column the decision variable best matches? The column values are an ordered set of numeric values. Is ceil or floor appropriate for a linear model?
2) Is there some way to then pick out that desired column, all of this without implementing integer/binary/nonlinear elements?
Any thoughts or advice on how to structure/formulate this would be greatly appreciated. I read somewhere that you can sometimes get around issues like this with constraints, but I was not able to get that to work....maybe this is worth
Robert Fourer
Convex piecewise-linear terms can be converted to continuous linear terms if and only if they are (1) in a minimize objective, (2) on the left-hand side of a <= constraint, or (3) on the right-hand side of a >= constraint. So it must be that your inequality constraint is not satisfying (2) or (3), and hence is not defining a convex region that can be represented by continuous linear constraints.
Right now you can't use any AMPL model with a variable or a parameter indexed ("subscripted") by an expression that contains a variable. If you try to solve with such a model, you'll get the "Variables in subscripts are not yet allowed" message.
Constraint programming is a different solving approach, which works best for very highly combinatorial problems -- ones that would otherwise require a lot of zero-one variables in the formulation. If your problem has a lot of continuous variables then constraint programming solvers are unlikely to be helpful; in fact the best-known one, ILOG CP, does not accept continuous variables. If you are using one of the standard linear programming solvers like MINOS, CPLEX, Gurobi, ... then you are not doing constraint programming, though of course you are building a model that involves constraints.
Paul mentioned constraint programming because some CP solvers accept "variables in subscripts" directly without any reformulation. But while we are planning such a feature, it is not available currently.
On Behalf Of bethanyc
Sent: Wednesday, February 13, 2013 8:44 PM
To: am...@googlegroups.com
Cc: 4...@ampl.com
Subject: Re: [AMPL 6625] selecting subset of table parameter values based on variable values
I'm not sure if my last post went through (it's not showing up), but I just discovered something else in my code that needs mentioning....
I had changed my "variable index" to a parameter, just to get things going, and I just remembered to change it back to a variable. When I imbed my linear piecewise expression (with the "variable index" as a parameter) directly in the constraint (inequality), it solves my model as an MIP. But when I change this index back to a variable, it gives me an error ("Variables in subscripts are not yet allowed") and will not solve at all.
I'm not sure if I'm really using "constraint programming" (I basically just removed the defined variable altogether and replaced its use in the constraint with the raw linear piecewise expression) but this is not working. Am I doing something wrong? I need the model to be linear, without integers or binary variables (so the Z(c) approach won't work). It sounds like constraint programming could work (per Paul's response) - can you explain in more detail how to use this?
And even if I have to scrap the variable index (and use a parameter instead), I don't understand why it treats the model as an MIP in that case. I had a similar experience recently, but it was because I was using a linear piecewise expression in an equality constraint, but this is an inequality constraint. And the piecewise expression is convex. Any ideas?
Thanks again!!