AMPL doesn't optimize my objective function.

[Mariola Barceló]

Hi there,

I want to solve a simple facility location problem in wich we have nodes (N), trajectories (T) and a weight between nodes and trajectories weight[t,n]. My variable x {N} is binary and it indicates if the corresponding node belongs to the solution set (or not).

 I implement the next objective function:

                            maximize f: 

                            sum{t in T} max {n in N} weight[t,n]*x[n];

I want that my objective function sums for each trajectory (t) the maximum weight weight[t,n] such that "n" is in the solution set (its value is 1).  It is subject to a cardinality constraint (the number of nodes in the solution set must be less or equal than k).

AMPL doesn't detect any error in my formulation but it doesn't optimize my problem (It returns me all the variables equal  to zero) and I think it could be because the objective function formulation is not correct.

Thanks.

[AMPL Google Group]

All solvers can maximize, but most cannot handle a "max" function inside the objective expression. When presented with "max", many solvers display an error message and do not return any solution, with the result that the solution remains at what it was before -- usually, all zeros. One exception that works with AMPL is LINDO Global, which can maximize your objective as it is written.

If you do not have access to LINDO Global, what solvers are available to you? There are ways to transform a model so that it does not explicitly use "max" and can be handled by other solvers. This involves adding many new zero-one variables and constraints, but still it is often effective.

--
Robert Fourer
am...@googlegroups.com

{#HS:1628159914-106241#}

--
You received this message because you are subscribed to the Google Groups "AMPL Modeling Language" group.
To unsubscribe from this group and stop receiving emails from it, send an email to ampl+uns...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/ampl/da8fd2d9-7225-42fc-8293-812b41986704n%40googlegroups.com.

[Daniel M. T.]

Hi,

You can easily linealize your expression. 

Make a new variable maxt{T}, the constraint are

R1{t in T, n in N}:  maxt[t] <= weight[t,n]*x[n];

Then your objective function might be 

Maximize z: sum{t in T} maxt[t] ;

Regards, 

To view this discussion on the web visit https://groups.google.com/d/msgid/ampl/reply-77152-1628159914-4749240731-1631476846-2125209248%40helpscout.net.

[AMPL Google Group]

The constraints "maxt[t] <= weight[t,n] * x[n]" imply that maxt[t] <= min {n in N} weight[t,n] * x[n]. Thus unfortunately they do not help in linearizing max {n in N} weight[t,n] * x[n] as requested in this question.

You can write instead "maxt[t] >= weight[t,n] * x[n]", which correctly implies that maxt[t] >= max {n in N} weight[t,n] * x[n]. But to ensure that max[y] equals max {n in N} weight[t,n] * x[n], you also need constraints that enforce maxt[t] <= max {n in N} weight[t,n] * x[n], and I don't know a way to formulate those without introducing a binary variable for each term weight[t,n] * x[n].

--
Robert Fourer
am...@googlegroups.com

{#HS:1628159914-106241#}

On Mon, Sep 13, 2021 at 1:49 PM UTC, AMPL Modeling Language <am...@googlegroups.com> wrote:

Hi,

You can easily linealize your expression.

Make a new variable maxt{T}, the constraint are

R1{t in T, n in N}: maxt[t] <= weight[t,n]*x[n];

Then your objective function might be

Maximize z: sum{t in T} maxt[t] ;

Regards,

On Sun, Sep 12, 2021 at 8:00 PM UTC, AMPL Google Group <am...@googlegroups.com> wrote:

All solvers can maximize, but most cannot handle a "max" function inside the objective expression. When presented with "max", many solvers display an error message and do not return any solution, with the result that the solution remains at what it was before -- usually, all zeros. One exception that works with AMPL is LINDO Global, which can maximize your objective as it is written.

If you do not have access to LINDO Global, what solvers are available to you? There are ways to transform a model so that it does not explicitly use "max" and can be handled by other solvers. This involves adding many new zero-one variables and constraints, but still it is often effective.

--
Robert Fourer
am...@googlegroups.com