« Previous « Start » Next »
F Conflict refiner, IIS, SA and Warm Start
It is possible to perform infeasibility and sensitivity analysis
with TOMLAB /CPLEX. The inputs and outputs are described in detail
in Section
A.1 and
A.2.
F.1 Conflict refiner
A conflict is a set of mutually contradictory constraints and bounds
within a model. Given an infeasible model, TOMLAB /CPLEX can
identify conflicting constraints and bounds within it. TOMLAB /CPLEX
refines an infeasible model by examining elements that can be
removed from the conflict to arrive at a minimal conflict. A
conflict smaller than the full model may make it easier for the user
to analyze the source of infeasibilities in the original model.
If the model happens to contain multiple independent causes of
infeasibility, it may be necessary for the user to repair one cause
and then repeat the process with a further refinement.
A file included in the TOMLAB distribution to enable easy use of the
feature.
F.1.1 cpxBuildConflict
Purpose
cpxBuildConflict provides a shortcut for generating conflict
refinement groups, for use with the Conflict Refinement feature of
TOMLAB /CPLEX.
Calling Syntax
(1) function confgrps = cpxBuildConflict(Prob,mode)
OR
(2) function confgrps = cpxBuildConflict(n,m_lin,m_quad,m_sos,m_ind,'mode')
Description of Inputs
| The following inputs are used: |
| |
| Inputs for (1): function confgrps =
cpxBuildConflict(Prob,mode |
| |
| Prob |
TOMLAB problem structure, describing a LP/QP/MILP/MIQP/MIQQ problem. |
| |
| mode |
String indicating which type of conflict group set is
desired. |
| |
A 'full' conflict group set will consist of one group for each
individual variable (upper+lower bound), linear, quadratic, sos
and indicator constraint in the problem. This will be very
large group set. |
| |
A 'minimal' set consists of at the most 6 groups: one each for all
variable lower+upper bounds, linear, sos, indicator, quad
constraints. |
| |
| Inputs for (2): function confgrps =
cpxBuildConflict(n,m_lin,m_quad,m_sos,m_ind,'mode') |
| |
| n |
Number of variables |
| m_lin |
Number of linear constraints |
| m_quad |
Number of quadratic constraints |
| m_sos |
Number of SOS constraints |
| m_ind |
Number of indicator constraints |
| mode |
Mode indicator as described above |
| |
Description
The confgrps is used as an input to
cplex.m or
cplexTL.m.
IIS is obsolete in the latest version of TOMLAB /CPLEX.
If TOMLAB /CPLEX reports that your problem is infeasible, then you
can invoke the TOMLAB /CPLEX infeasibility finder to help you
analyze the source of the infeasibility. This diagnostic tool
computes a set of infeasible constraints and column bounds that
would be feasible if one of them (a constraint or variable) were
removed. Such a set is known as an irreducibly inconsistent set
(IIS).
To work, the infeasibility finder must have a problem that satisfies
two conditions:
- the problem has been optimized by the primal or dual simplex
optimizer or by the barrier optimizer with crossover, and
- the optimizer has terminated with a declaration of
infeasibility.
Correcting Multiple Infeasibilities
The infeasibility finder will find only one irreducibly inconsistent
set (IIS), though a given problem may contain many independent IISs.
Consequently, even after you detect and correct one such IIS in your
problem, it may still remain infeasible. In such a case, you need to
run the infeasibility finder more than once to detect those multiple
causes of infeasibility in your problem.
Interpreting IIS Output
The size of the IIS reported by TOMLAB /CPLEX depends on many
factors in the model. If an IIS contains hundreds of rows and
columns, you may find it hard to determine the cause of the
infeasibility. Fortunately, there are tactics to help you interpret
IIS output:
- Consider selecting an alternative IIS algorithm. The default algorithm emphasizes computation speed, and it may give rise to a relatively large IIS. See parameter IISIND.
- If the problem contains equality constraints, examine the cumulative constraint consisting of the sum of the equality rows.
- Try preprocessing with the TOMLAB /CPLEX presolver and aggregator. The
presolver may even detect infeasibility by itself. If not, running
the infeasibility finder on the presolved problem may help by
reducing the problem size and removing extraneous constraints that
do not directly cause the infeasibility but still appear in the IIS.
Similarly, running the infeasibility finder on an aggregated problem
may help because the aggregator performs substitutions that may
remove extraneous variables that clutter the IIS output. More
generally, if you perform substitutions, you may simplify the output
so that it can be interpreted more easily.
- Other simplifications of the constraints in the IIS, such as
combining variables, multiplying constraints by constants, and
rearranging sums, may make it easier to interpret the IIS.
The availability of a basis for an LP allows you to perform
sensitivity analysis for your model, if it is an LP. Such analysis
tells you by how much you can modify your model without affecting
the solution you found. The modifications supported by the
sensitivity analysis function include bound changes, changes of the
right hand side vector and changes of the objective function.
F.4 Warm Start
When solving a large number of small and similar LP problems with
the same size it is recommended to use TOMLAB /CPLEX in a slightly
different manner to avoid unnecessary overhead and preserve memory.
This objective is achieved by calling
cplexmex directly as
done internally in
cplex.
A call to
cplexmex will return a basis, which can be used to
efficiently warm start the solution process of a modified problem.
The following code exemplifies the process. In general it is
recommended to use the TOMLAB format as well and compare solutions
to make sure that the problem is correctly entered.
% See cplex.m to backtrack the inputs.
%
Prob = lpAssign(...);
PriLev = 0;
basis = [];
[x, slack, v, rc, f_k, ninf, sinf, Inform, basis] = ...
cplexmex(Prob.QP.c, sparse([]), sparse(Prob.A), zeros(12,1) , ...
Prob.x_L, Prob.x_U, Prob.b_L, Prob.b_U, 1e20, 1, PriLev, Prob, ...
zeros(Prob.N,1), [], [], [], [], [], [], [], ...
[], [], [], [], [], [], [], basis);
% Change the problem and input the basis returned above
Prob.x_L(1) = 2;
[x, slack, v, rc, f_k, ninf, sinf, Inform, basis] = ...
cplexmex(Prob.QP.c, sparse([]), sparse(Prob.A), zeros(12,1) , ...
Prob.x_L, Prob.x_U, Prob.b_L, Prob.b_U, 1e20, 1, PriLev, Prob, ...
zeros(Prob.N,1), [], [], [], [], [], [], [], ...
[], [], [], [], [], [], [], basis);
« Previous « Start » Next »
TOMLAB
