SCIP
Solving Constraint Integer Programs
Solving Constraint Integer Programs
Subtour elimination constraint handler for TSP problems, written in C++.
Definition in file ConshdlrSubtour.cpp.
#include <cassert>#include <string>#include <iostream>#include "ConshdlrSubtour.h"#include "GomoryHuTree.h"#include "objscip/objscip.h"#include "scip/cons_linear.h"Go to the source code of this file.
Functions | |
| static SCIP_Bool | findSubtour (SCIP *scip, GRAPH *graph, SCIP_SOL *sol) |
| static SCIP_RETCODE | sepaSubtour (SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS **conss, int nconss, int nusefulconss, SCIP_SOL *sol, SCIP_RESULT *result) |
| SCIP_DECL_CONSDELETE (ConshdlrSubtour::scip_delete) | |
| SCIP_DECL_CONSTRANS (ConshdlrSubtour::scip_trans) | |
| SCIP_DECL_CONSSEPALP (ConshdlrSubtour::scip_sepalp) | |
| SCIP_DECL_CONSSEPASOL (ConshdlrSubtour::scip_sepasol) | |
| SCIP_DECL_CONSENFOLP (ConshdlrSubtour::scip_enfolp) | |
| SCIP_DECL_CONSENFOPS (ConshdlrSubtour::scip_enfops) | |
| SCIP_DECL_CONSCHECK (ConshdlrSubtour::scip_check) | |
| SCIP_DECL_CONSPROP (ConshdlrSubtour::scip_prop) | |
| SCIP_DECL_CONSLOCK (ConshdlrSubtour::scip_lock) | |
| SCIP_DECL_CONSDELVARS (ConshdlrSubtour::scip_delvars) | |
| SCIP_DECL_CONSPRINT (ConshdlrSubtour::scip_print) | |
| SCIP_DECL_CONSHDLRCLONE (ObjProbCloneable *ConshdlrSubtour::clone) | |
| SCIP_DECL_CONSCOPY (ConshdlrSubtour::scip_copy) | |
| scip | SCIP data structure |
| graph | underlying graph |
| sol | proposed solution |
Definition at line 44 of file ConshdlrSubtour.cpp.
References GraphEdge::adjac, GraphEdge::back, FALSE, GraphNode::first_edge, GraphEdge::next, nnodes, Graph::nnodes, Graph::nodes, NULL, SCIP_Bool, SCIPgetSolVal(), TRUE, and GraphEdge::var.
Referenced by SCIP_DECL_CONSCHECK(), SCIP_DECL_CONSENFOLP(), and SCIP_DECL_CONSENFOPS().
|
static |
| scip | SCIP data structure |
| conshdlr | the constraint handler itself |
| conss | array of constraints to process |
| nconss | number of constraints to process |
| nusefulconss | number of useful (non-obsolete) constraints to process |
| sol | primal solution that should be separated |
| result | pointer to store the result of the separation call |
Definition at line 118 of file ConshdlrSubtour.cpp.
References GraphEdge::adjac, GraphEdge::back, GraphEdge::cap, Graph::edges, FALSE, GraphNode::first_edge, ghc_tree(), GraphNode::id, Graph::nedges, GraphEdge::next, Graph::nnodes, Graph::nodes, NULL, GraphEdge::rcap, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_OKAY, SCIP_SEPARATED, SCIPaddCut(), SCIPaddVarToRow(), SCIPallocBufferArray, SCIPcacheRowExtensions(), SCIPconsGetData(), SCIPcreateEmptyRowCons(), SCIPfeastol(), SCIPflushRowExtensions(), SCIPfreeBufferArray, SCIPgetSolVal(), SCIPinfinity(), SCIPisCutEfficacious(), SCIPreleaseRow(), TRUE, and GraphEdge::var.
Referenced by SCIP_DECL_CONSSEPALP(), and SCIP_DECL_CONSSEPASOL().
| SCIP_DECL_CONSDELETE | ( | ConshdlrSubtour::scip_delete | ) |
frees specific constraint data
WARNING! There may exist unprocessed events. For example, a variable's bound may have been already changed, but the corresponding bound change event was not yet processed.
Definition at line 223 of file ConshdlrSubtour.cpp.
References NULL, release_graph(), SCIP_OKAY, and SCIPfreeBlockMemory.
| SCIP_DECL_CONSTRANS | ( | ConshdlrSubtour::scip_trans | ) |
transforms constraint data into data belonging to the transformed problem
Definition at line 235 of file ConshdlrSubtour.cpp.
References capture_graph(), NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemory, SCIPconsGetData(), SCIPconsGetName(), SCIPconsIsChecked(), SCIPconsIsDynamic(), SCIPconsIsEnforced(), SCIPconsIsInitial(), SCIPconsIsLocal(), SCIPconsIsModifiable(), SCIPconsIsPropagated(), SCIPconsIsRemovable(), SCIPconsIsSeparated(), SCIPconsIsStickingAtNode(), and SCIPcreateCons().
| SCIP_DECL_CONSSEPALP | ( | ConshdlrSubtour::scip_sepalp | ) |
separation method of constraint handler for LP solution
Separates all constraints of the constraint handler. The method is called in the LP solution loop, which means that a valid LP solution exists.
The first nusefulconss constraints are the ones, that are identified to likely be violated. The separation method should process only the useful constraints in most runs, and only occasionally the remaining nconss - nusefulconss constraints.
possible return values for *result (if more than one applies, the first in the list should be used):
Definition at line 277 of file ConshdlrSubtour.cpp.
References NULL, SCIP_CALL, SCIP_OKAY, and sepaSubtour().
| SCIP_DECL_CONSSEPASOL | ( | ConshdlrSubtour::scip_sepasol | ) |
separation method of constraint handler for arbitrary primal solution
Separates all constraints of the constraint handler. The method is called outside the LP solution loop (e.g., by a relaxator or a primal heuristic), which means that there is no valid LP solution. Instead, the method should produce cuts that separate the given solution.
The first nusefulconss constraints are the ones, that are identified to likely be violated. The separation method should process only the useful constraints in most runs, and only occasionally the remaining nconss - nusefulconss constraints.
possible return values for *result (if more than one applies, the first in the list should be used):
Definition at line 304 of file ConshdlrSubtour.cpp.
References SCIP_CALL, SCIP_OKAY, and sepaSubtour().
| SCIP_DECL_CONSENFOLP | ( | ConshdlrSubtour::scip_enfolp | ) |
constraint enforcing method of constraint handler for LP solutions
The method is called at the end of the node processing loop for a node where the LP was solved. The LP solution has to be checked for feasibility. If possible, an infeasibility should be resolved by branching, reducing a variable's domain to exclude the solution or separating the solution with a valid cutting plane.
The enforcing methods of the active constraint handlers are called in decreasing order of their enforcing priorities until the first constraint handler returned with the value SCIP_CUTOFF, SCIP_SEPARATED, SCIP_REDUCEDDOM, SCIP_CONSADDED, or SCIP_BRANCHED. The integrality constraint handler has an enforcing priority of zero. A constraint handler which can (or wants) to enforce its constraints only for integral solutions should have a negative enforcing priority (e.g. the alldiff-constraint can only operate on integral solutions). A constraint handler which wants to incorporate its own branching strategy even on non-integral solutions must have an enforcing priority greater than zero (e.g. the SOS-constraint incorporates SOS-branching on non-integral solutions).
The first nusefulconss constraints are the ones, that are identified to likely be violated. The enforcing method should process the useful constraints first. The other nconss - nusefulconss constraints should only be enforced, if no violation was found in the useful constraints.
possible return values for *result (if more than one applies, the first in the list should be used):
Definition at line 342 of file ConshdlrSubtour.cpp.
References findSubtour(), NULL, SCIP_Bool, SCIP_FEASIBLE, SCIP_INFEASIBLE, SCIP_OKAY, and SCIPconsGetData().
| SCIP_DECL_CONSENFOPS | ( | ConshdlrSubtour::scip_enfops | ) |
constraint enforcing method of constraint handler for pseudo solutions
The method is called at the end of the node processing loop for a node where the LP was not solved. The pseudo solution has to be checked for feasibility. If possible, an infeasibility should be resolved by branching, reducing a variable's domain to exclude the solution or adding an additional constraint. Separation is not possible, since the LP is not processed at the current node. All LP informations like LP solution, slack values, or reduced costs are invalid and must not be accessed.
Like in the enforcing method for LP solutions, the enforcing methods of the active constraint handlers are called in decreasing order of their enforcing priorities until the first constraint handler returned with the value SCIP_CUTOFF, SCIP_REDUCEDDOM, SCIP_CONSADDED, SCIP_BRANCHED, or SCIP_SOLVELP.
The first nusefulconss constraints are the ones, that are identified to likely be violated. The enforcing method should process the useful constraints first. The other nconss - nusefulconss constraints should only be enforced, if no violation was found in the useful constraints.
If the pseudo solution's objective value is lower than the lower bound of the node, it cannot be feasible and the enforcing method may skip it's check and set *result to SCIP_DIDNOTRUN. However, it can also process its constraints and return any other possible result code.
possible return values for *result (if more than one applies, the first in the list should be used):
Definition at line 396 of file ConshdlrSubtour.cpp.
References findSubtour(), NULL, SCIP_Bool, SCIP_FEASIBLE, SCIP_INFEASIBLE, SCIP_OKAY, and SCIPconsGetData().
| SCIP_DECL_CONSCHECK | ( | ConshdlrSubtour::scip_check | ) |
feasibility check method of constraint handler for primal solutions
The given solution has to be checked for feasibility.
The check methods of the active constraint handlers are called in decreasing order of their check priorities until the first constraint handler returned with the result SCIP_INFEASIBLE. The integrality constraint handler has a check priority of zero. A constraint handler which can (or wants) to check its constraints only for integral solutions should have a negative check priority (e.g. the alldiff-constraint can only operate on integral solutions). A constraint handler which wants to check feasibility even on non-integral solutions must have a check priority greater than zero (e.g. if the check is much faster than testing all variables for integrality).
In some cases, integrality conditions or rows of the current LP don't have to be checked, because their feasibility is already checked or implicitly given. In these cases, 'checkintegrality' or 'checklprows' is FALSE.
possible return values for *result:
Definition at line 441 of file ConshdlrSubtour.cpp.
References findSubtour(), NULL, SCIP_Bool, SCIP_CALL, SCIP_FEASIBLE, SCIP_INFEASIBLE, SCIP_OKAY, SCIPconsGetData(), SCIPinfoMessage(), and SCIPprintCons().
| SCIP_DECL_CONSPROP | ( | ConshdlrSubtour::scip_prop | ) |
domain propagation method of constraint handler
The first nusefulconss constraints are the ones, that are identified to likely be violated. The propagation method should process only the useful constraints in most runs, and only occasionally the remaining nconss - nusefulconss constraints.
possible return values for *result:
Definition at line 486 of file ConshdlrSubtour.cpp.
References NULL, SCIP_DIDNOTRUN, and SCIP_OKAY.
| SCIP_DECL_CONSLOCK | ( | ConshdlrSubtour::scip_lock | ) |
variable rounding lock method of constraint handler
This method is called, after a constraint is added or removed from the transformed problem. It should update the rounding locks of all associated variables with calls to SCIPaddVarLocks(), depending on the way, the variable is involved in the constraint:
Consider the linear constraint "3x -5y +2z <= 7" as an example. The variable rounding lock method of the linear constraint handler should call SCIPaddVarLocks(scip, x, nlocksneg, nlockspos), SCIPaddVarLocks(scip, y, nlockspos, nlocksneg) and SCIPaddVarLocks(scip, z, nlocksneg, nlockspos) to tell SCIP, that rounding up of x and z and rounding down of y can destroy the feasibility of the constraint, while rounding down of x and z and rounding up of y can destroy the feasibility of the constraint's negation "3x -5y +2z > 7". A linear constraint "2 <= 3x -5y +2z <= 7" should call SCIPaddVarLocks(scip, ..., nlockspos + nlocksneg, nlockspos + nlocksneg) on all variables, since rounding in both directions of each variable can destroy both the feasibility of the constraint and it's negation "3x -5y +2z < 2 or 3x -5y +2z > 7".
If the constraint itself contains other constraints as sub constraints (e.g. the "or" constraint concatenation "c(x) or d(x)"), the rounding lock methods of these constraints should be called in a proper way.
Consider the or concatenation "c(x) or d(x)". The variable rounding lock method of the or constraint handler should call SCIPaddConsLocks(scip, c, nlockspos, nlocksneg) and SCIPaddConsLocks(scip, d, nlockspos, nlocksneg) to tell SCIP, that infeasibility of c and d can lead to infeasibility of "c(x) or d(x)".
As a second example, consider the equivalence constraint "y <-> c(x)" with variable y and constraint c. The constraint demands, that y == 1 if and only if c(x) is satisfied. The variable lock method of the corresponding constraint handler should call SCIPaddVarLocks(scip, y, nlockspos + nlocksneg, nlockspos + nlocksneg) and SCIPaddConsLocks(scip, c, nlockspos + nlocksneg, nlockspos + nlocksneg), because any modification to the value of y or to the feasibility of c can alter the feasibility of the equivalence constraint.
Definition at line 542 of file ConshdlrSubtour.cpp.
References Graph::edges, Graph::nedges, NULL, SCIP_CALL, SCIP_OKAY, SCIPaddVarLocks(), SCIPconsGetData(), and GraphEdge::var.
| SCIP_DECL_CONSDELVARS | ( | ConshdlrSubtour::scip_delvars | ) |
variable deletion method of constraint handler
This method should iterate over all constraints of the constraint handler and delete all variables that were marked for deletion by SCIPdelVar().
input:
Definition at line 572 of file ConshdlrSubtour.cpp.
References SCIP_OKAY.
| SCIP_DECL_CONSPRINT | ( | ConshdlrSubtour::scip_print | ) |
constraint display method of constraint handler
The constraint handler should store a representation of the constraint into the given text file.
Definition at line 582 of file ConshdlrSubtour.cpp.
References Graph::nedges, Graph::nnodes, NULL, SCIP_OKAY, SCIPconsGetData(), and SCIPinfoMessage().
| SCIP_DECL_CONSHDLRCLONE | ( | ObjProbCloneable *ConshdlrSubtour::clone | ) |
clone method which will be used to copy a objective plugin
Definition at line 599 of file ConshdlrSubtour.cpp.
| SCIP_DECL_CONSCOPY | ( | ConshdlrSubtour::scip_copy | ) |
constraint copying method of constraint handler
The constraint handler can provide a copy method, which copies a constraint from one SCIP data structure into a other SCIP data structure.
Definition at line 610 of file ConshdlrSubtour.cpp.
References capture_graph(), FALSE, tsp::ProbDataTSP::getGraph(), NULL, SCIP_CALL, SCIP_OKAY, SCIP_PLUGINNOTFOUND, SCIPallocBlockMemory, SCIPconsGetName(), SCIPcreateCons(), SCIPerrorMessage, SCIPfindConshdlr(), and SCIPgetObjProbData().