Break after 1 hour

[sebastia...@gmail.com]

Hello everyone,

I have written programs in AMPL that often take a long time to solve optimally. I know from scientific papers that the researchers sometimes stop early (after 1hr) if no solution has been generated by then.
How is it possible in AMPL that either
- the optimal solution is given or
- after one hour it is terminated and the solution generated until then is output.

Unfortunately I could not find a solution myself so far.

Thanks a lot for the help!
Kind regards, Sebastian

[AMPL Google Group]

Most solvers have a stopping option based on time. If the solver has not found a provably optimal solution after a given number of seconds, the solver stops and returns the best solution that it has found so far. Each solver has its own way of stating this option, however. Which solver (or solvers) are you trying to use?

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

{#HS:1403984250-98930#}

[sebastia...@gmail.com]

Hello Mr. Fourer,

I use clpex as solver and have the command

option cplex_options "timelimit = 3600";

to limit the calculation to one hour.
And "_solve_elapsed_time" seems to me to be basically the most appropriate command to display the time if the solution was generated within one hour.

However, a few more questions now arise. I have uploaded my files for this purpose. The problems are machine scheduling problems for a single machine.

1)
When I solve problem M2_wC_ohne_r (time-indexed variables), I get a solution to my small problem fairly quickly and in the console all results appear quickly.
For M4_wC_without_r (assignment and position data variables), the line "CPLEX 12.10.0.0: timelimit = 120" appears in the console only after about 30 seconds. What is this time needed for? Does this have any meaning?

2)
My problem M3_wC_without_r (linear assignment variables) cannot be solved. I get these error messages, but can't figure out why:

presolve, variable delta[40,40]:
    impossible deduced bounds: lower = 1, upper = 0
presolve, variable delta[39,39]:
    impossible deduced bounds: lower = 1, upper = 0
presolve, variable delta[38,38]:
    impossible deduced bounds: lower = 1, upper = 0
presolve, variable delta[37,37]:
    impossible deduced bounds: lower = 1, upper = 0
presolve, variable delta[36,36]:
    impossible deduced bounds: lower = 1, upper = 0
75 presolve messages suppressed.

Thanks for the help!

Kind regards
Sebastian

The programs are based on the paper by Keha et al. (2009):
Keha, Ahmet, Khowala, Ketan, Fowler, John (2009): Mixed integer programming formula-tions for single machine scheduling problems. In: Computers & Industrial Engineering, Vol. 56(1): 357-367.

[sebastia...@gmail.com]

Unfortunately, I can not upload my files. Are there any restrictions I need to follow?

[sebastia...@gmail.com]

[sebastia...@gmail.com]

Sorry, but i can't upload the files. So here is the copy.

DataSet.dat

param n := 40;
param Q := 0.4;        # Einzelwert
param L := 0.5;        # {0.5,0.7}
param R := 0.4;        # {0.4,0.8,1.4}
param p_max := 10;
param w_max := 10;

M1-M4.run

reset;
model alleM.mod;
data DataSet.dat;

param d{j in J} >= 0;

for {j in J}    {
    let p[j] := trunc(Uniform(1, p_max + 1));
    let w[j] := trunc(Uniform(1, w_max + 1));
}

let M := sum{j in J} p[j];            # Wird im Paper Keha et al. (2009) mit P angegeben

let T := trunc(3/2 * M);
    
for {j in J}    {
    let d[j] := trunc(Uniform(M*(L-R/2),M*(L+R/2)+1));
    let r[j] := trunc(Uniform(0, Q*M + 1));
}

let Mr := M + max{j in J} r[j];  

option solver cplex;
option cplex_solve_system_time 0;
option cplex_options "timelimit = 120";


problem M1_wC_ohne_r: weighted_C_M1, LB, disjunctive1_ohne_r, disjunctive2_ohne_r, C_ohne_r, C, y;

problem M1_wC_mit_r: weighted_C_M1, LB, disjunctive1_mit_r, disjunctive2_mit_r, C_mit_r, C, y;

problem M2_wC_ohne_r: weighted_C_M2, assignment, start, x;

problem M2_wC_mit_r: weighted_C_M2, assignment, start, release, x;

problem M3_wC_ohne_r: weighted_C_M3, C3_ohne_r, precedence, transitivity, delta;

problem M3_wC_mit_r: weighted_S_M3, C3_mit_r_1, C3_mit_r_2, precedence, transitivity, delta, S;

problem M4_wC_ohne_r: weighted_C_M4, assignment_job, assignment_position, gamma_1, gamma_k, C4_ohne_r, u, gamma, C4;

problem M4_wC_mit_r: weighted_C_M4, assignment_job, assignment_position, gamma_1, gamma_k, C4_mit_r_1, C4_mit_r_2, u, gamma, C4;

[AMPL Google Group]

1. When I run case M4_wC_ohne_r, I see immediately this output:

ampl: include M1-M4.run
ampl: solve M4_wC_ohne_r;
CPLEX 20.1.0.0: timelimit = 120

At the beginning of a CPLEX run, "CPLEX 20.1.0.0:" is always displayed, followed by the options that have been set for the run. In this case, the only option is "timelimit = 120". After 120 seconds, CPLEX displays another message that indicates the time limit has been reached:

CPLEX 20.1.0.0: time limit with integer solution; objective 15510
197482 MIP simplex iterations
1217 branch-and-bound nodes
absmipgap = 15007.7, relmipgap = 0.967612
ampl:

At this point, the best solution that CPLEX has found, with objective value 15510, has been returned. Are you having a different experience? You mention something that is happening in 30 seconds, but I am not sure what that is.

2. AMPL has not sent your problem to the solver, because its presolve phase has analyzed the constraints (including the bounds on the variables) and has determined that no feasible solution is possible. With your model and data, presolve gives reasons like this:

presolve, variable delta[40,40]:
impossible deduced bounds: lower = 1, upper = 0

Because delta is a binary variable, this can be interpreted as follows: Using some of the constraints and bounds on other variables, presolve could deduce that delta[40,40] must be 0 in any feasible solution; but using other constraints and bounds, presolve could deduce that delta[40,40] must be 1. Since delta[40,40] can't be both 0 and 1, it must be that no feasible solution can exist.

There is no simple and general way to deal with an error like this, but it is possible to suggest some good ways to get started. As an initial troubleshooting step, it is often helpful to use AMPL's expand command to see see whether AMPL generated the constraints that you expected. By itself, expand; shows all of the constraints. If there are many of them, you can use, for example, expand expand C3_ohne_r; to expand all of the constraints that have a particular name. Also you can write, for instance, expand >listing.txt; or expand expand C3_ohne_r >listing.txt; to send all of the output to the file listing.txt.

You can also use a command like display C3.lb, C3.ub; to see all of the lower and upper bounds that presolve deduced on a variable.

You should also consider using AMPL's drop and restore commands to narrow your search for the cause of the infeasibility. If you drop some constraints and the resulting problem is still infeasible, then you don't need to consider the dropped constraints in looking for the cause of infeasibility. By trying a series of drops, you may be able to determine that infeasibility is being caused by only a small subset of the constraints.

If you are using one of the popular MIP solvers (CPLEX, Gurobi, Xpress) then to get more help with diagnosing the infeasibility, you can ask the solver to compute an irreducible infeasible subset. For more on this topic, search "IIS" at groups.google.com/group/ampl, and also see the discussion of "infeasibility diagnosis" in chapter 14 of the AMPL book (https://ampl.com/BOOK/CHAPTERS/17-solvers.pdf#page=25).

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

{#HS:1403984250-98930#}

On Mon, Jan 25, 2021 at 8:00 PM UTC, AMPL Modeling Language <am...@googlegroups.com> wrote:

sebastia...@gmail.com schrieb am Montag, 25. Januar 2021 um 20:48:01 UTC+1:

On Mon, Jan 25, 2021 at 7:48 PM UTC, AMPL Modeling Language <am...@googlegroups.com> wrote:

Unfortunately, I can not upload my files. Are there any restrictions I need to follow?

On Sun, Jan 24, 2021 at 10:07 PM UTC, AMPL Google Group <am...@googlegroups.com> wrote:

Most solvers have a stopping option based on time. If the solver has not found a provably optimal solution after a given number of seconds, the solver stops and returns the best solution that it has found so far. Each solver has its own way of stating this option, however. Which solver (or solvers) are you trying to use?

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

[sebastia...@gmail.com]

Hello Mr. Fourer,

thank you very much for the detailed answer and the hints. In fact, the problem was trivial. I simply forgot the decision variable "C3" when listing the problems. I also adjusted a constraint (as shown in Ying et al. (2019))

Before:

subject to precedence {j in J, k in J: 1 <= j <= k <= n}:
    delta[j,k] + delta[k,j] = 1;

problem M3_wC_ohne_r: weighted_C_M3, C3_ohne_r, precedence, transitivity, delta;

Now:

subject to precedence {j in J, k in J: j <> k}:                      
    delta[j,k] + delta[k,j] = 1;

problem M3_wC_ohne_r: weighted_C_M3, C3_ohne_r, precedence, transitivity, delta, C3;

The other "problem" remains. When I load the run file and enter the command "solve M4_wC_ohne_r;" and confirm, a few seconds pass before the line "CPLEX 12.10.0.0 timelimit =120" appears.
This does not happen if I want to solve the problems M1, M2 or M3. In the end, I still get a solution after 120 seconds, so that's not a big deal. I'm just surprised that it only happens with M4.

Ying, K-C., Cheng, C.-Y., Lin, S.-W., Hung, C.-H. (2019): Comparative analysis of mixed integer programming formulations for single-machine and parallel-machine scheduling problems.

[AMPL Google Group]

By running with "option times 1;" I was able to confirm that solve M4_wC_ohne_r is taking only a small fraction of a second to generate the problem and send it to CPLEX.

Which platform are you running on? One thing we have observed previously is that when running under Windows 10, there is often a delay like you describe before the first solve with CPLEX. But then there is no delay before later solves. However we have not been able to reproduce a situation where solve M4_wC_ohne_r always has a brief delay before the CPLEX solver starts, but there is never such a delay for solve M1_wC_ohne_r or the other cases.

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

{#HS:1403984250-98930#}

On Wed, Jan 27, 2021 at 12:41 PM UTC, AMPL Modeling Language <am...@googlegroups.com> wrote:

Hello Mr. Fourer,

thank you very much for the detailed answer and the hints. In fact, the problem was trivial. I simply forgot the decision variable "C3" when listing the problems. I also adjusted a constraint (as shown in Ying et al. (2019))

Before:
subject to precedence {j in J, k in J: 1 <= j <= k <= n}:
delta[j,k] + delta[k,j] = 1;

problem M3_wC_ohne_r: weighted_C_M3, C3_ohne_r, precedence, transitivity, delta;

Now:
subject to precedence {j in J, k in J: j <> k}:
delta[j,k] + delta[k,j] = 1;

problem M3_wC_ohne_r: weighted_C_M3, C3_ohne_r, precedence, transitivity, delta, C3;

The other "problem" remains. When I load the run file and enter the command "solve M4_wC_ohne_r;" and confirm, a few seconds pass before the line "CPLEX 12.10.0.0 timelimit =120" appears.
This does not happen if I want to solve the problems M1, M2 or M3. In the end, I still get a solution after 120 seconds, so that's not a big deal. I'm just surprised that it only happens with M4.

Ying, K-C., Cheng, C.-Y., Lin, S.-W., Hung, C.-H. (2019): Comparative analysis of mixed integer programming formulations for single-machine and parallel-machine scheduling problems.

On Tue, Jan 26, 2021 at 8:41 PM UTC, AMPL Google Group <am...@googlegroups.com> wrote:

1. When I run case M4_wC_ohne_r, I see immediately this output:

ampl: include M1-M4.run
ampl: solve M4_wC_ohne_r;
CPLEX 20.1.0.0: timelimit = 120

At the beginning of a CPLEX run, "CPLEX 20.1.0.0:" is always displayed, followed by the options that have been set for the run. In this case, the only option is "timelimit = 120". After 120 seconds, CPLEX displays another message that indicates the time limit has been reached:

CPLEX 20.1.0.0: time limit with integer solution; objective 15510
197482 MIP simplex iterations
1217 branch-and-bound nodes
absmipgap = 15007.7, relmipgap = 0.967612
ampl:

At this point, the best solution that CPLEX has found, with objective value 15510, has been returned. Are you having a different experience? You mention something that is happening in 30 seconds, but I am not sure what that is.

2. AMPL has not sent your problem to the solver, because its presolve phase has analyzed the constraints (including the bounds on the variables) and has determined that no feasible solution is possible. With your model and data, presolve gives reasons like this:

presolve, variable delta[40,40]:
impossible deduced bounds: lower = 1, upper = 0

Because delta is a binary variable, this can be interpreted as follows: Using some of the constraints and bounds on other variables, presolve could deduce that delta[40,40] must be 0 in any feasible solution; but using other constraints and bounds, presolve could deduce that delta[40,40] must be 1. Since delta[40,40] can't be both 0 and 1, it must be that no feasible solution can exist.

There is no simple and general way to deal with an error like this, but it is possible to suggest some good ways to get started. As an initial troubleshooting step, it is often helpful to use AMPL's expand command to see see whether AMPL generated the constraints that you expected. By itself, expand; shows all of the constraints. If there are many of them, you can use, for example, expand expand C3_ohne_r; to expand all of the constraints that have a particular name. Also you can write, for instance, expand >listing.txt; or expand expand C3_ohne_r >listing.txt; to send all of the output to the file listing.txt.

You can also use a command like display C3.lb, C3.ub; to see all of the lower and upper bounds that presolve deduced on a variable.

You should also consider using AMPL's drop and restore commands to narrow your search for the cause of the infeasibility. If you drop some constraints and the resulting problem is still infeasible, then you don't need to consider the dropped constraints in looking for the cause of infeasibility. By trying a series of drops, you may be able to determine that infeasibility is being caused by only a small subset of the constraints.

If you are using one of the popular MIP solvers (CPLEX, Gurobi, Xpress) then to get more help with diagnosing the infeasibility, you can ask the solver to compute an irreducible infeasible subset. For more on this topic, search "IIS" at groups.google.com/group/ampl, and also see the discussion of "infeasibility diagnosis" in chapter 14 of the AMPL book (https://ampl.com/BOOK/CHAPTERS/17-solvers.pdf#page=25).

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