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

[jerron Liu]

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. I want AMPL only calculates once and uses the different part of the same result in different places of this model. How to do so with 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 to maximize a single value, as the calculation result. And it was used only once and does not appear again in the constraint.

[AMPL Google Group]

You can declare R as a "defined variable", like this:

param m integer > 0;
param n integer > 0;
param p {1..m, 1..n};
var X {1..m} integer; # also >= 0 ?

var R {j in 1..n} = sum {i in 1..m} X[i] * p[i,j];

Then in your objective and constraints you can refer to R[1], R[2], etc.

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

{#HS:925289468-51852#}

--
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/2227f88e-5003-435e-b119-241159c28ec5%40googlegroups.com.

[jerron liu]

Thanks. Now I'm able to send the request to Neos. However I didn't get the expected result. Can you help to check what is wrong?

Attached please find a demo spread sheet demo.xlsx, in which excel solver successfully found a solution. Also please find the ampl.mod and ampl.dat files.  I submitted them to neos/cplex. What I got are all zeros:

*************************************************************

   NEOS Server Version 5.0

   Disclaimer:

   This information is provided without any express or
   implied warranty. In particular, there is no warranty
   of any kind concerning the fitness of this
   information  for any particular purpose.
*************************************************************
Job 7437387 has finished.
File exists
You are using the solver cplexamp.
Checking ampl.mod for cplex_options...
Executing AMPL.
processing data.
processing commands.
Executing on prod-exec-5.neos-server.org

Presolve eliminates 1 constraint and 1 variable.
Substitution eliminates 17 variables.
Adjusted problem:
16 variables, all nonlinear
5 constraints; 76 nonzeros
	2 nonlinear constraints
	3 linear constraints
	5 inequality constraints
1 linear objective; 16 nonzeros.

CPLEX 12.7.0.0: threads=4
CPLEX 12.7.0.0: Constraint _scon[1] is a nonquadratic nonlinear constraint.
_display 1 1 16
positions
0,0
1,0
2,0
3,0
4,0
5,0
6,0
7,0
8,0
9,0
10,0
11,0
12,0
13,0
14,0
15,0
_display 1 1 5
R0
0,0
1,0
2,0
3,0
4,0
_display 1 1 5
R1
0,0
1,0
2,0
3,0
4,0

To view this discussion on the web visit https://groups.google.com/d/msgid/ampl/reply-77152-925289468-2596174212-1565356716-638442842%40helpscout.net.

[AMPL Google Group]

You have received this error message from CPLEX:

CPLEX 12.7.0.0: Constraint _scon[1] is a nonquadratic nonlinear constraint.

This means that CPLEX encountered some functions that were not linear or quadratic. As a result it rejected your problem, and when you displayed the variables, they were all at still at their default values of 0.

In your example, it is easy to see that the nonlinear functions are min, max, and count. These will have to be linearized to permit CPLEX to be used. Instead of

var costloss = min {i in prices} min(R0[i],R1[i]);
subject to Lossreg: costloss >= maxloss;

you will have to write

var M;
subj to Mdef0 {i in prices}: M <= R0[i];
subj to Mdef1 {i in prices}: M <= R1[i];

subject to Lossreg: M >= maxloss;

Here M is <= all R0[i] and R1[i], so it is <= their min. Since maxloss is <= M, it must also be <= their min.

The other nonlinearity, involving costsize and Sizereg, is harder. You could use the following:

param U = 1000;
var MAX;
var MIN;
var POS {insts} binary;
var NEG {insts} binary;
subj to MAXdef {i in insts}: MAX >= positions[i];
subj to MINdef {i in insts}: MIN <= positions[i];
subj to POSdef {i in insts}: U * POS[i] >= positions[i];
subj to NEGdef {i in insts}: -U * NEG[i] <= positions[i];

subject to Sizereg: MAX - MIN +
(sum {i in insts} POS[i])^2 + (sum {i in insts} NEG[i])^2 <= maxsize;

I will leave it to you to figure out why this should work. But notice that when the integer variable positions[i] is positive, POS[i] must be 1, while otherwise it may be zero; and similarly for NEG[i].

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

{#HS:925289468-51852#}

On Fri, Aug 9, 2019 at 1:18 PM UTC, AMPL Google Group <am...@googlegroups.com> wrote:

You can declare R as a "defined variable", like this:

param m integer > 0;
param n integer > 0;
param p {1..m, 1..n};
var X {1..m} integer; # also >= 0 ?

var R {j in 1..n} = sum {i in 1..m} X[i] * p[i,j];

Then in your objective and constraints you can refer to R[1], R[2], etc.

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

[jerron liu]

It works like a charm. Thank you very much!

To view this discussion on the web visit https://groups.google.com/d/msgid/ampl/reply-77152-925289468-2602434953-1565644995-1946809794%40helpscout.net.

[jerron liu]

When I appled the similar logic to a bigger problem I got another error . Can you please extend another help?

p.s. when I see the message like "logical constraint _slogcon[1] is not an indicator constraint.", how do I know which constraint causing the complaint?

Here is the full out put and Attached please find the model and data.

File exists
You are using the solver cplexamp.
Checking ampl.mod for cplex_options...

Checking ampl.com for cplex_options...

Executing AMPL.
processing data.
processing commands.

Executing on prod-exec-1.neos-server.org
Presolve eliminates 3 constraints and 1 variable.
Substitution eliminates 141 variables.
Adjusted problem:
219 variables:
216 nonlinear variables
3 linear variables
335 algebraic constraints; 4079 nonzeros
1 nonlinear constraint
334 linear constraints
335 inequality constraints
2 logical constraints
1 linear objective; 0 nonzeros.
CPLEX 12.7.0.0: threads=4
CPLEX 12.7.0.0: logical constraint _slogcon[1] is not an indicator constraint.
_display 1 1 72
diffs
1,0
2,0

... (all 0s)

[AMPL Google Group]

To see which constraint is _slogcon[1], look at
_slogconname[1]:

ampl: print _slogconname[1];
Timegain

The trouble with Timegain is that you use the and operator:

subject to Timegain: R1[10]>=0.1 and R1[9]>=-R1[11];

Instead you should use two separate subject to statements, one specifying R1[10]>=0.1 and the other specifying R1[9]>=-R1[11]. Also you can't use and in constraint Upgain, but there you should create an indexed constraint: "subject to Upgain {j in 1..5}: R1[j] >= upgain;". (In general, CPLEX does not recognize the and operator and the or operator in constraints.)

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

{#HS:925289468-51852#}

On Mon, Aug 12, 2019 at 10:44 PM UTC, AMPL Modeling Language <am...@googlegroups.com> wrote:

It works like a charm. Thank you very much!

[jerron liu]

Again, thank you very much! Is there a document where I can find such tricks/tips ?

To view this discussion on the web visit https://groups.google.com/d/msgid/ampl/reply-77152-925289468-2605286051-1565724970-1219711962%40helpscout.net.

[jerron liu]

Since I submitted the problem in NEOS, 7 hours passed and it is still running. Is it normal it take so long? In excel same problem only takes 30 - 50 minutes. Maybe because excel solver only gives local optimal? Is there any way we can speed it up? Also where else can we get more powerful calculations?

[AMPL Google Group]

Sometimes CPLEX finds an optimal solution quickly but takes a very long time to prove optimality. To see what is going on, create an AMPL commands file for NEOS containing these lines:

option cplex_options 'mipdisplay 2 timelimit 3600';
solve;

(If you are already using a commands file for NEOS, add the above option statement to it.) Specify your commands file in addition to your model and data files when you submit your job to NEOS.

You will then see a progress log from CPLEX, with the best objective value so far in the "Best Integer" column, and the currently known upper bound on the objective in the "Best Bound" column. (Scroll down to see the most recent line.) CPLEX will stop when Best Integer and Best Bound are within 0.01%, but with the above cplex_options settings it will also stop after 3600 seconds (which you can change to any other value you like).

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

{#HS:925289468-51852#}

On Wed, Aug 14, 2019 at 4:38 AM UTC, AMPL Modeling Language <am...@googlegroups.com> wrote:

Since I submitted the problem in NEOS, 7 hours passed and it is still running. Is it normal it take so long? In excel same problem only takes 30 - 50 minutes. Maybe because excel solver only gives local optimal? Is there any way we can speed it up? Also where else can we get more powerful calculations?

On Tue, Aug 13, 2019 at 9:43 PM UTC, AMPL Modeling Language <am...@googlegroups.com> wrote:

Again, thank you very much! Is there a document where I can find such tricks/tips ?

On Tue, Aug 13, 2019 at 7:35 PM UTC, AMPL Google Group <am...@googlegroups.com> wrote:

To see which constraint is _slogcon[1], look at
_slogconname[1]:

ampl: print _slogconname[1];
Timegain

The trouble with Timegain is that you use the and operator:

subject to Timegain: R1[10]>=0.1 and R1[9]>=-R1[11];

Instead you should use two separate subject to statements, one specifying R1[10]>=0.1 and the other specifying R1[9]>=-R1[11]. Also you can't use and in constraint Upgain, but there you should create an indexed constraint: "subject to Upgain {j in 1..5}: R1[j] >= upgain;". (In general, CPLEX does not recognize the and operator and the or operator in constraints.)

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

[jerron Liu]

after I changed the time limit to 10 minutes, the result was already good enough. Thanks.

However, when I change the size limit from

param U = 1000;

var MAXdiffs;

var MINdiffs;

var POSdiffs {insts} binary;

var NEGdiffs {insts} binary;

subj to MAXdef {i in insts}: MAXdiffs >= diffs[i];

subj to MINdef {i in insts}: MINdiffs <= diffs[i];

subj to diffsdef {i in insts}: U * POSdiffs[i] >= diffs[i];

subj to NEGdef {i in insts}: -U * NEGdiffs[i] <= diffs[i];

var sizereg=MAXdiffs - MINdiffs + 

(sum {i in insts} POSdiffs[i])^2*5 + (sum {i in insts} NEGdiffs[i])^2*5 ;

subject to Sizereg: sizereg<= maxsize;

to

param U = 1000;

var POSdiffs {insts} binary;

var NEGdiffs {insts} binary;

subj to diffsdef {i in insts}: U * POSdiffs[i] >= diffs[i];

subj to NEGdef {i in insts}: -U * NEGdiffs[i] <= diffs[i];

var sizereg=(sum {i in insts} (POSdiffs[i] - NEGdiffs[i])*diffs[i]) + 

5*(sum {i in insts} POSdiffs[i])^2 + 5*(sum {i in insts} NEGdiffs[i])^2;

subject to Sizereg: sizereg<= maxsize;

I got an error: 

CPLEX 12.7.0.0: QP Hessian is not positive semi-definite.

0 MIP simplex iterations

0 branch-and-bound nodes

No basis.

How to fix it?

Attached please find the mod and data.

To unsubscribe from this group and stop receiving emails from it, send an email to am...@googlegroups.com.

[AMPL Google Group]

In your constraint Sizereg, you have introduced a quadratic expression sum {i in insts} (POSdiffs[i] - NEGdiffs[i])*diffs[i] that is not convex. As result, CPLEX cannot handle your constraint. (The message "QP Hessian is not positive semi-definite" is a technical way of saying this.) Since your new quadratic terms POSdiffs[i] * diffs[i] and NEGdiffs[i] * diffs[i] have the special form of a binary variable times a general variable, you could linearize them as explained by Paul Rubin at https://orinanobworld.blogspot.com/2010/10/binary-variables-and-quadratic-terms.html.

You could also try solving for a local optimum with Knitro or for a global optimum with BARON, as those are more general nonlinear solvers that will accept any quadratic expression in the constraints. However, when a special linearization is available, it often gives better results.

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

{#HS:925289468-51852#}

On Wed, Aug 14, 2019 at 2:22 PM UTC, AMPL Google Group <am...@googlegroups.com> wrote:

Sometimes CPLEX finds an optimal solution quickly but takes a very long time to prove optimality. To see what is going on, create an AMPL commands file for NEOS containing these lines:

option cplex_options 'mipdisplay 2 timelimit 3600';
solve;

(If you are already using a commands file for NEOS, add the above option statement to it.) Specify your commands file in addition to your model and data files when you submit your job to NEOS.

You will then see a progress log from CPLEX, with the best objective value so far in the "Best Integer" column, and the currently known upper bound on the objective in the "Best Bound" column. (Scroll down to see the most recent line.) CPLEX will stop when Best Integer and Best Bound are within 0.01%, but with the above cplex_options settings it will also stop after 3600 seconds (which you can change to any other value you like).

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

[jerron Liu]

I followed the idea in the blog and rewrote the model. Attached please find the model file and data file. They were accepted. But CPLEX can not give me a solution. It took less than 1 second and told me "No basis". I knew it would not be hard to find a solution meeting all the constraints.  For example, diffs[10]=-10 and diffs[51]=15 and all others zero. Shall I give the solver a feasible start point? If so, how to do that?

also from the result, I can see the binary variables didn't meet the constraints -- POSdiffs is set to 1 for negative diffs.

Thank you very much!

Here is the output:

Total (root+branch&cut) =    0.33 sec. (297.35 ticks)
CPLEX 12.7.0.0: optimal integer solution within mipgap or absmipgap; objective 1265.23368
5192 MIP simplex iterations
755 branch-and-bound nodes
absmipgap = 0.0429868, relmipgap = 3.39754e-05
No basis.
_display 1 1 72
diffs
1,0
2,0
3,0
4,0
5,0
6,0
7,0
8,0
9,0
10,0
11,0
12,0
13,0
14,0
15,0
16,0
17,0
18,-757
19,-1000
20,0

...

[jerron Liu]

What I tried to achieve is to limit the sum of absolute value of each diffs plus the square of the count of non zero diffs, less than a given number maxsize. I.E.,

s.t. (sum{i in insts} |diffs[i]|) + (count{i in insts} diffs[i]<>0)^2*5 <=maxsize; 

[jerron Liu]

I changed the model to like following:

param U = 1000;

var POSdiffs {insts} binary;

var NEGdiffs {insts} binary;

subj to POSdef {i in insts}: U * POSdiffs[i] >= diffs[i];

subj to NEGdef {i in insts}: -U * NEGdiffs[i] <= diffs[i];

var absdiffs{insts} >=0;

subj to ABSD1{i in insts}:absdiffs[i]>=diffs[i];

subj to ABSD2{i in insts}:-absdiffs[i]<=diffs[i];

var sizereg=(sum {i in insts} absdiffs[i] ) + 5*(sum {i in insts} POSdiffs[i])^2 + 5*(sum {i in insts} NEGdiffs[i])^2;

subject to Sizereg: sizereg<= maxsize;

However I still can't get a solution although we know there is solution (for example diffs[13]=-10, diffs[51]=15; all others 0):

	Total (root+branch&cut) =    0.76 sec. (603.66 ticks)
	CPLEX 12.7.0.0: optimal integer solution within mipgap or absmipgap; objective 506.252217
	5516 MIP simplex iterations
	605 branch-and-bound nodes
	absmipgap = 0.048029, relmipgap = 9.48718e-05
	No basis.

Can you please help?

[AMPL Google Group]

CPLEX reports finding an optimal solution to your problem:

CPLEX http://12.7.0.0/: optimal integer solution within mipgap or absmipgap; objective 506.252217

5516 MIP simplex iterations
605 branch-and-bound nodes
absmipgap = 0.048029, relmipgap = 9.48718e-05

The message "No basis" means that CPLEX did not return simplex basis statuses for the continuous variables, but since there is seldom any reason to want those statuses anyway, you can ignore this message. (We are trying to get rid of it, actually.)

POSdiffs and NEGdiffs are both defined to be zero-one (binary) variables. Your constraints say that POSdiffs[i] will be 1 if diffs[i] is positive, and NEGdiffs[i] will be 1 if diffs[i] is negative. The command "display diffs, POSdiffs, NEGdiffs;" will show the results clearly.

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

{#HS:925289468-51852#}

On Fri, Aug 16, 2019 at 2:04 AM UTC, AMPL Modeling Language <am...@googlegroups.com> wrote:

I changed the model to like following:

param U = 1000;
var POSdiffs {insts} binary;
var NEGdiffs {insts} binary;

subj to POSdef {i in insts}: U * POSdiffs >= diffs;
subj to NEGdef {i in insts}: -U * NEGdiffs <= diffs;
var absdiffs{insts} >=0;
subj to ABSD1{i in insts}:absdiffs>=diffs;
subj to ABSD2{i in insts}:-absdiffs<=diffs;
var sizereg=(sum {i in insts} absdiffs ) + 5*(sum {i in insts} POSdiffs)^2 + 5*(sum {i in insts} NEGdiffs)^2;

subject to Sizereg: sizereg<= maxsize;

However I still can't get a solution although we know there is solution (for example diffs[13]=-10, diffs[51]=15; all others 0):

Total (root+branch&cut) = 0.76 sec. (603.66 ticks)

CPLEX http://12.7.0.0/: optimal integer solution within mipgap or absmipgap; objective 506.252217

5516 MIP simplex iterations
605 branch-and-bound nodes
absmipgap = 0.048029, relmipgap = 9.48718e-05
No basis.

Can you please help?

On Thu, Aug 15, 2019 at 11:49 PM UTC, AMPL Modeling Language <am...@googlegroups.com> wrote:

What I tried to achieve is to limit the sum of absolute value of each diffs plus the square of the count of non zero diffs, less than a given number maxsize. I.E.,

On Thu, Aug 15, 2019 at 11:35 PM UTC, AMPL Modeling Language <am...@googlegroups.com> wrote:

I followed the idea in the blog and rewrote the model. Attached please find the model file and data file. They were accepted. But CPLEX can not give me a solution. It took less than 1 second and told me "No basis". I knew it would not be hard to find a solution meeting all the constraints. For example, diffs[10]=-10 and diffs[51]=15 and all others zero. Shall I give the solver a feasible start point? If so, how to do that?
also from the result, I can see the binary variables didn't meet the constraints -- POSdiffs is set to 1 for negative diffs.
Thank you very much!
Here is the output:

Total (root+branch&cut) = 0.33 sec. (297.35 ticks)
CPLEX 12.7.0.0: optimal integer solution within mipgap or absmipgap; objective 1265.23368
5192 MIP simplex iterations
755 branch-and-bound nodes
absmipgap = 0.0429868, relmipgap = 3.39754e-05
No basis.

_display 1 1 72
diffs
1,0
2,0

3,0
4,0
5,0
6,0
7,0
8,0
9,0
10,0
11,0
12,0
13,0
14,0
15,0

16,0
17,0
18,-757
19,-1000
20,0

...

On Thu, Aug 15, 2019 at 2:36 PM UTC, AMPL Google Group <am...@googlegroups.com> wrote:

In your constraint Sizereg, you have introduced a quadratic expression sum {i in insts} (POSdiffs[i] - NEGdiffs[i])*diffs[i] that is not convex. As result, CPLEX cannot handle your constraint. (The message "QP Hessian is not positive semi-definite" is a technical way of saying this.) Since your new quadratic terms POSdiffs[i] * diffs[i] and NEGdiffs[i] * diffs[i] have the special form of a binary variable times a general variable, you could linearize them as explained by Paul Rubin at https://orinanobworld.blogspot.com/2010/10/binary-variables-and-quadratic-terms.html.

You could also try solving for a local optimum with Knitro or for a global optimum with BARON, as those are more general nonlinear solvers that will accept any quadratic expression in the constraints. However, when a special linearization is available, it often gives better results.

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

[jerron liu]

Thank you so much!

I did not realize it is the right answer, just because it is too fast to believe. 😂

--

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/reply-77152-925289468-2612769678-1565964169-652925332%40helpscout.net.