CODEWITHSUNDEEP
ampl
jerron
jerron

Reputation: 343

In AMPL, how to refer to part of the result, and use them in multiple places

I'm learning AMPL to speed up a model currently in excel spreadsheet with excel solver. It basically based on the matrix multiplication result of a 1 x m variables and an m x n parameters. And it would find the variables to maximize the minimum of certain values in the result while keeping some other values in the same result satisfying a few constraints. How to do so in AMPL?


Given: P= m x n parameters
Variable: X= 1 x m variable we tried to solve
Calculate: R= X x P , result of matrix multiplication of X and P
Maximize: min(R[1..3]), the minimum value of the first 3 values in the result
Subject to: R[2]<R[4]
            min(R[6..8])>20
            R[5]-20>R[7]
            X are all integers

I read several tutorials and look up the manual but can't find the solution to this seemingly straightforward problem. All I found is maximize a single value, which is the calculation result. And it was used only once and does not appear again in the constraint.

Upvotes: 1

Views: 584

Answers (1)

G_B
G_B

Reputation: 1573

The usual approach for "maximize the minimum" problems in products like AMPL is to define an auxiliary variable and set linear constraints that effectively define it as the minimum, converting a nonlinear function (min) into linear rules.

For instance, suppose I have a bunch of decision variables x[i] with i ranging over an index set S, and I want to maximize the minimum over x[i]. AMPL syntax for that would be:

var x_min;
s.t. DefineMinimum{i in S}: x_min <= x[i];
maximize ObjectiveFunction: x_min;

The constraint only requires that x_min be less than or equal to the minimum of x[i]. However, since you're trying to maximize x_min and there are no other constraints on it, it should always end up exactly equal to that minimum (give or take machine-arithmetic epsilon considerations).

If you have parameters (i.e. values are known before you run the optimisation) and want to refer to their minimum, AMPL lets you do that more directly:

param p_min := min{j in IndexSet_P} p[j];

While AMPL also supports this syntax for variables, not all of the solvers used with AMPL are capable of accepting this type of constraint. For instance:

reset;
option solver gecode;
set S := {1,2,3};
var x{S} integer;
var x_min = min{s in S} x[s];
minimize OF: sum{s in S} x[s];
s.t. c1: x_min >= 5;
solve;

This will run and do what you'd expect it to do, because Gecode is programmed to recognise and deal with min-type constraints. However, if you switch the solver option to gurobi or cplex it will fail, since these only accept linear or quadratic constraints. To apply a minimum constraint with those solvers, you need to use something like the linearization trick I discussed above.

Upvotes: 1

Related Questions