1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ You are looking for variable purchase to be either 0 or [min, max] value? $\endgroup$ Mar 6, 2023 at 14:19
  • 1
    $\begingroup$ See or.stackexchange.com/questions/6545/… for a linearization. $\endgroup$
    – RobPratt
    Mar 6, 2023 at 17:15
  • $\begingroup$ @Sutanu Yes. Customer may buy in exact dollar amount or not buy at all (=0). $\endgroup$ Mar 6, 2023 at 21:19
  • $\begingroup$ @wanderinganon Ok, then you can use the answer below or the answer in the link above. Both are the same, it forces the purchase to choose from a set which includes 0, onwards. You can easily generate such a set in Python. $\endgroup$ Mar 6, 2023 at 21:34

3 Answers 3

1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ By " automatically linearizes var purchase {CUSTOMER} in VALUE" you mean the set can't be expressed in reals because AMPL turns them into integers? Your proposed solution does work for me in AMPL so long as the solver is of the kind that admits mixed-integer problem statements (e.g. Couenne). However, the wider the range between min_amt and max_amt (the cardinality of the set) the higher the chance the solver will crash with some exit code on my system. $\endgroup$ Mar 7, 2023 at 10:52
  • $\begingroup$ I rewrote the explanation so that it uses a set of reals. You just need to change max_amt to 100 or whatever value you want. By "automatically linearizes" I mean that AMPL constructs an equivalent problem that replaces the requirement var purchase {CUSTOMER} in VALUE by an equivalent statement using some extra binary variables and a linear constraint. $\endgroup$
    – 4er
    Mar 7, 2023 at 16:39
0
$\begingroup$

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] $

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.