search

IBMDecisionOptimization / docplex-examples

These samples demonstrate how to use the DOcplex library to model and solve optimization problems.
https://ibmdecisionoptimization.github.io/
Apache License 2.0
396 stars 229 forks source link

Information on infeasible/unbounded model #35

Closed jiedxu closed 4 years ago

jiedxu commented 4 years ago

Hi. Thanks for effort at docplex and this repo. I like Writing efficient DOcplex code and Correcting infeasible models a lot.

I am wondering if there is more detailed information if a MILP model is infeasible or unbounded.

The status in docplex.mp.sdetails.SolveDetails alone is not really helpful, and None is returned instead of docplex.mp.solution.SolveSolution.

jiedxu commented 4 years ago

I found docplex.mp.relaxer really helpful. But is there an easier way?

PhilippeCouronne commented 4 years ago

Hi. Can you elaborate on why the status information is not helpful? What status message do you get?

There is an alternative to Relaxer, which is the conflict refiner. However, this refiner gives you a (minimal) set of constraints which cause the infeasibility, but may time quite along time to finish.

About the relaxer, can you share your feedback in using it, and how we could improve it? Thanks

jiedxu commented 4 years ago

Thanks for the quick response. My model (for unit commitment of electricity generations) can be optimally solved when I test it with short time periods. But it becomes infeasible when longer periods are considered.

When it is infeasible, here is the info in SolveDetails.

                                 value
best_bound                         NaN
columns                       64800738
mip_relative_gap                   NaN
nb_iterations                        0
nb_linear_nonzeros           265452771
nb_nodes_processed                   0
problem_type                      MILP
status              integer infeasible
status_code                        103
time                           141.394
has_hit_limit                    False

I will try relaxer and conflict refiner and summarise my approach in the coming days, but I do hope the process can be done automatically by telling which constraints cause the infeasibility directly.

Also, there might be some incorrect entries in my data set. I am wondering if to define constants using docplex.mp.params.parameters can help me locate those entries.

PhilippeCouronne commented 4 years ago

From the details, it looks like there is no integer solution. It might help to see the CPLEX log, it might give some information.

For data analysis, set parameter "read.datacheck" to 2: at beginning of solve, it will analyse your data for ill-conditioning and report issues. If you have questions on the output, post warnings here.

Below Docplex code to enable data checking:

mdl.parameters.read.datacheck = 2

jiedxu commented 4 years ago

It might help to see the CPLEX log, it might give some information.

Is this the CPLEX log you referred? I set read.datacheck and mdl.solve(log_output=f'log_output.txt'). (I only paste a small portion of the warnings).

Version identifier: 12.10.0.0 | 2019-11-26 | 843d4de
CPXPARAM_Read_DataCheck                          2
CPXPARAM_RandomSeed                              201903125
CPLEX Warning  1057: the objective vector has almost equal coefficients for variable 'flow_2017-12-24 11:00:00+00:00_EVO_7797181_SPLITHIGH10_EVO_7796456_SPLITHIGH10' and variable 'flow_2017-12-24 11:00:00+00:00_EVO_7797324_SPLITHIGH10_EVO_7796781_SPLITHIGH10'.
CPLEX Warning  1057: Too many warnings of this type have been detected.  All further warnings of this type will be ignored.
CPLEX Warning  1062: Detected objective coefficients that may be suited for multiobjective optimization.

Tried aggregator 2 times.
MIP Presolve eliminated 763 rows and 764 columns.
Aggregator did 12887 substitutions.
Reduced MIP has 28794 rows, 28796 columns, and 102357 nonzeros.
Reduced MIP has 0 binaries, 14018 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.09 sec. (63.27 ticks)
Found incumbent of value 0.000430 after 0.22 sec. (147.24 ticks)
Tried aggregator 1 time.
Detecting symmetries...
Reduced MIP has 28794 rows, 28796 columns, and 102357 nonzeros.
Reduced MIP has 0 binaries, 14018 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.10 sec. (49.26 ticks)
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: deterministic, using up to 4 threads.
Root relaxation solution time = 0.16 sec. (74.98 ticks)

        Nodes                                         Cuts/
   Node  Left     Objective  IInf  Best Integer    Best Bound    ItCnt     Gap

*     0+    0                            0.0004        0.0000           100.00%
*     0     0      integral     0        0.0004        0.0004     1344    0.00%
Elapsed time = 0.56 sec. (310.86 ticks, tree = 0.00 MB, solutions = 2)

Root node processing (before b&c):
  Real time             =    0.57 sec. (312.98 ticks)
Parallel b&c, 4 threads:
  Real time             =    0.00 sec. (0.00 ticks)
  Sync time (average)   =    0.00 sec.
  Wait time (average)   =    0.00 sec.
                          ------------
Total (root+branch&cut) =    0.57 sec. (312.98 ticks)

This problem with one timestamp can be solved optimally. I am waiting for results with 168 timestamps.

jiedxu commented 4 years ago

Could you please give me some hints on how to use docplex.mp.params.parameters. Do you think it helps if I define parameters clearly and set read.datacheck?

Or is that module purely designed for setting parameters in CPLEX rather than constants in my models?

PhilippeCouronne commented 4 years ago
  1. Yes, this is the CPLEX log I was referring to. Option "read.datacheck=2" shows minor potential issues in objective, nothing which may explain/cause an infeasibility. Enable the log on the largest instance, it may happen that CPLEX detect and displays which constraint is infeasible.

About parameters: model.parameters is a recursive tree structure which contains CPLEX parameters. read.datacheck=2 performs "model assistance", that is checks the problem coefficients for potential numerical issues.

It also checks for nans and infinities; is that what you refer to as "incorrect data"? I see no problem of that kind in your log. CPLEX cannot do any semantic check beyond searching for NaNs or infinite values; semantic checking (i.e. which depends on the application) must be done by custom code.

More information about modeling assistance here: https://www.ibm.com/support/knowledgecenter/SSSA5P_12.10.0/ilog.odms.cplex.help/CPLEX/UsrMan/topics/progr_consid/modelingAssistance/introModelingAssistance.html

jiedxu commented 4 years ago

Thanks for the elaboration.

PhilippeCouronne commented 4 years ago

@edxu96 Still, I would like to comment on the relaxer. The relaxer acts like a (smart) rewrite of the model which in the end starts a MIP solve. By default it does two things: find minimum relaxation, then finds optimal objective, compatible with this minimal relaxation. It is possible to skip pass #2 (optimal objective) and just look for a feasible solution, by passing a relax_mode='MinSum' argument to relax().

relaxer.relax(model, log_output=False, relax_mode='MinSum')

Finally, the relaxer performs a MIP search, which you can control with the usual techniques: gap, time limit.. Running a limited search may not prove the optimality of the relaxation but will give you a relaxed solution together with information about which constraints were relaxed...

To summarize:

Hope this helps.