Step function constraints: Approximate with piecewise linear functions or ?

[Ellen]

I have a series of constraints that are step functions. E.g., y=1 for
x in [0,10], y=2 for x in (10,20], y=3 for x in (20,30], etc. In the
small version of my problem, I successfully used binary varibles. But
now for the really big version ...

I have tried to approximate this as a piecewise linear function for
which

breakpoints are 10, 10.1, 20, 20.1, 30, etc. and
slopes are 0, 100, 0, 100, 0, etc. (assuming my
arithmetic for this example is correct).

Cplex gives me the error message, "contains a nonquadratic nonlinear
constraint".

A colleague gave me a hint that piecewise linear functions' slopes
must be always increasing or always decreasing (and that one is
preferred but he couldn't remember which) but of course my slopes
increase from 0 to 100 then decrease from 100 to 0, then increase ...

Any thoughts would be much appreciated.

Regards,
Ellen Fowler

[Paul]

Have you tried your binary approach in the "really big version", or are you just going with the general rule of thumb that proliferation of binary variables = really slow solution time?  Each step function becomes an SOS1 constraint, and SOS1 constraints aren't all that scary.  Although contemporary MIP solvers seem to be pretty good at identifying SOS1 constraints on their own, you could try declaring them explicitly, which would let you assign a weight to each binary variable.  (I would try the y values as the weights.)

Paul

[Robert Fourer]

Because your piecewise-linear function does not have increasing slopes, it
is not convex. If you express it using AMPL's piecewise-linear notation,
then CPLEX can deal with the nonconvexity, but only by introducing integer
variables; CPLEX has some clever ways of doing this, but even so you will
very likely end up with a harder problem than your original one in which you
represented the step function exactly. For the example you give, your
constraints could be as simple as x <= 10*y, if the objective insures that y
will never be larger than necessary. Otherwise you could use 10*(y-1) <= x
and x <= 10*y. (This still leaves a little ambiguity -- y can be 3 or 4,
say, when x is 30 -- but there's no avoiding that given that you can't use <
and > constraints, only <= and >= ones.)

The "contains a nonquadratic nonlinear constraint" message suggests that
your model used something other than AMPL's piecewise-linear notation --
maybe "if" statements? -- which to CPLEX looked only like some
other-than-linear expression that it's not designed to handle.

Bob Fourer
4...@ampl.com

[Ellen]

Thanks, Paul and Bob, for these suggestions. I will think them out.
Yes, I was avoiding binary variables per that rule of thumb.

Another colleague suggested I keep my original binary formulation but
always provide a recent solution for the starting point before solving
for a new solution. That might eliminate most of the solving time.

Regards,
Ellen Fowler

> > Ellen Fowler- Hide quoted text -
>
> - Show quoted text -