Optimization solver that satisfies variable values within set membership

Question

Is there a solver that can handle an AMPL model of this sort:

param max_amt=1;
param min_amt=.05;
set VALUE={min_amt..max_amt by .01}union{0}; # Exact dollar value
var purchase {CUSTOMER} in VALUE; # set membership as opposed to inequality/equality
# Maximize or minimize some utility non-linear function...

In other words, a non-linear solver that can satisfy a set membership constrain in continuous domain.

Answer 1

AMPL automatically linearizes var purchase {CUSTOMER} in VALUE; where VALUE is a set of numbers. The linearization creates some binary (zero-one) variables, so you need a solver that can handle such variables.

However, due to the limited precision of floating-point arithmetic in the computer, sets of fractional values like {min_amt..max_amt by .01} are problematical. Here's a simplified example of one kind of unexpected result: If you define

param min_amt := 0.05;
ampl: param max_amt := 0.22;
ampl: set VALUE = {0} union {min_amt..max_amt by .01};

then using AMPL's display command, you can look at the members of the set VALUE:

ampl: display VALUE;
set VALUE :=
0                      0.1                    0.16
0.05                   0.11                   0.16999999999999998
0.060000000000000005   0.12000000000000001    0.18
0.07                   0.13                   0.19
0.08                   0.14                   0.2
0.09                   0.15000000000000002    0.21000000000000002;

The number 0.22 is not in the set! This problem is really due to the use of by .01. The number .01 cannot be represented exactly in the computer, so when .01 is repeatedly added to min_amt, there is some imprecision in the results. In this example, when .01 is added to the previous value 0.21000000000000002, the result is 0.22000000000000003, which not included in the set because it is greater than max_amt. To be sure that you do not run into this and similar problems, you can instead define VALUE by a series of integers that are each divided by 100:

param min_amt := 5;
param max_amt := 22;
set VALUE = {0} union setof {i in min_amt..max_amt} i/100;

Then the members of VALUE are as expected:

ampl: display VALUE;
set VALUE :=
0      0.06   0.08   0.1    0.12   0.14   0.16   0.18   0.2    0.22
0.05   0.07   0.09   0.11   0.13   0.15   0.17   0.19   0.21;

When VALUE is defined in this way, the linearization of var purchase {CUSTOMER} in VALUE; will add some binary variables to your problem, but it will not change the members of VALUE -- they will still be fractional, and the values of the variable purchase will be fractional.

If you use this approach and still get crashes, you may want to report an example to the AMPL forum.

Answer 2

Define a set like $I= \{0,5,6,...100\}$ and a binary $z_i$.
Add constraints:
$ \sum_{i\in I} iz_{i,k} = 100p_k$ where $p$ is purchase variable for k customers
$ \sum_{i\in I} z_{i,k} = 1$
Above 2 will enforce purchase variable $p$ to choose from the set I

Or
Depending upon objective (if it's linear) you may choose purchase variable $p$ as belonging to domain non-negative integer $Z$ and with a binary $z_{k}$ you can have pair of constraints for all $k$ customers
$100*0.05z_{k} \le p_k \le 100z_k$.
This bounds in non-continuous 0 or $[5,...100] $

Answer 3

MINLP (Mixed-Integer Non-Linear Problem) solvers can process the optimization predicate of the question I asked of which Bonmin and Couenne are two FOSS examples, both natively supported in AMPL.

For such a solver the example stated can more suitably be expressed as:

param max_amt=1;
param min_amt=.05;
var purchase {CUSTOMER} in interval [min_amount,max_amt] union {0};

rounding purchase[] as round(purchase[],2) wherever it is inputted.

This so far has been the most efficient, least computationally intensive, remedy among the answers I've come across and won't lead to software crash as easily when the range between min_amt and max_amt enlarges.