help re-formulating a logical constraint

[james.co...@gmail.com]

Hi

I have a logical constraint that causing problems with my code. I have the following constraint in my problem:

subject to MaxCapacity { i in Set1, j in Set2} : Q[ i , j ] = min( sum{ k in Set3} Qbid[ j , k ] * Abid[ i , j , k ] , Q_max[ i , j ] ) ;

where Q and Qbid are variables and Abid and Q_max are parameters.

I tried solving the problem with ilogcp (with option ilogcp_options 'optimizer=cplex' ; ) but this resulted in an error 11. Cplex, Gurobi or Xpress weren't able to solve it. Knitro did something but said it ended up at an in-feasible point.

Any ideas on how I could re-formulate this to make it linear?

thanks
James

[james.co...@gmail.com]

I should have added: in words, the problem is about solving for bid curves, Qbid, in a market, subject to a (stochastic) market saturation level, Q_max. Set1 refers to the set of scenarios to convert my stochastic problem into its deterministic equivalent. Set2 is time. Set3 is set of pre-specified price points quantities bids must be made at. Abid is a parameter and represents whether or not a specific price point bid is accepted. Abid captures the stochastic processes.

Thus, a simpler formulation (removing the time dimension) is:

subject to MaxCapacity { i in Set1 } : Q[ i ] = min( sum{ k in Set3} Qbid[ k ] * Abid[ i , k ] , Q_max[ i ] ) ;

[Robert Fourer]

None of the solvers are likely to handle this "max" function well. If you can live with

Q[i,j] <= min( sum{k in Set3} Qbid[j,k] * Abid[i,j,k], Q_max[i,j] )

then you can replace this constraint with two constraints,

Q[i,j] <= sum{k in Set3} Qbid[j,k] * Abid[i,j,k]
Q[i,j] <= Q_max[i,j]

This sort of transformation works for many models, so you should consider it first. If however it happens that at an optimal solution both Q[i,j] < sum{k in Set3} Qbid[j,k] * Abid[i,j,k] and Q[i,j] < Q_max[i,j] for some i and j, then you are in a harder situation that will require some zero-one variables to force one of these to be an equality.

If you want to avoid figuring out the zero-one formulation, you can take advantage of the fact that Q_max is a param to use AMPL's piecewise-linear notation, though this will involve defining another variable:

Q_sum[i,j] = sum{k in Set3} Qbid[j,k] * Abid[i,j,k]
Q[i,j] = <<Q_max[i,j]; 1,0>> Q_sum[i,j]

Then AMPL will automatically add the needed zero-one variables to linearize the second constraint before sending the problem to a linear solver.

Bob Fourer
am...@googlegroups.com

=======

[james.co...@gmail.com]

Hi Robert

Thanks for the advice.

The piecewise-linear solution works perfectly.

kind regards

James