Scippy

SCIP

Solving Constraint Integer Programs

Release notes for SCIP 1.2

SCIP 1.2.0

Features

  • adjusted hard memory limit to (soft memory limit)*1.1 + 100mb in check.sh, checkcount.sh, check_cplex.sh, check_cluster.sh and check_cbc.sh
  • new presolving step in cons_knapsack.c, same like simplifyinequalities in cons_linear.c
  • now it's possible to write strings with more than SCIP_MAXSTRLEN amount of characters in all message.c functions
  • the current/root lp can be marked to be no relaxation of the current/root problem
  • added new preprocessing step (mergeMultiples) in cons_setppc.c where equal variables are merged
  • Black-box lexicographic dual simplex algorithm; can now run lexicographical dual algorithm (parameter lp/lexdualalgo)
  • Bounds:
    • SCIP now has lazy bounds, which are useful for column generation: see Further remarks pricer remarks for an explanation. Each variable has now two additional SCIP_Real parameter which define a lazy lower and upper bound; lazy means that there exists constraints which implies these (lazy) bounds. If the lazy lower or upper bound is greater or less than the local lower or upper bound, respectively, then the corresponding bound is not put into the LP. The bounds are set to minus and plus infinity per default which yields the same behavior as before. With the methods SCIPchgVarLbLazy() and SCIPchgVarUbLazy() these bounds can be set. This is of interest if SCIP gets used as a branch-and-price framework. Attention! The lazy bounds need to be valid for each feasible LP solution. If the objective function implies bounds on the variables for each optimal LP solution, but these bounds may be violated for arbitrary LP solutions, these bounds must not be declared lazy!
    • interval arithmetic functions can work with unbounded intervals added new functions to allow more operations on intervals, including solving quadratic interval equations
  • Branching:
    • extended hybrid relpscost branching rule by usage of the average length of conflicts a variable appears in
    • early branching-functionality added: in a branch-and-price code, the user can stop pricing at a node although there may exist variables with negative reduced costs. In this case, the lp-lowerbound will not be used. The pricer has, however, the option to return a lower bound. This can be useful for column generation.
  • Constraints:
    • Copy constructors and i/o functionality for constraints: all linear type constraint handlers are able to copy constraints using the function SCIPgetConsCopy() in scip.h
    • the linear constraint handler is able to parse a string in CIP format and create a corresponding linear constraint
    • Constraint handler for indicator constraints and parsing them from *.lp and *.zpl files
    • the indicator constraint can now try to produce a feasible solution (via heur_trysol)
    • one can now write indicator constraints in LP-format
    • added constraint handler for quadratic constraints
  • Cuts:
    • added new version of zerohalf cuts from Manuel Kutschka
    • added multi-commodity-flow cut separator
  • Heuristics:
    • Heuristics which are applied before root LP
    • added heuristic that performs a local search in an NLP (takes only linear and quadratic constraints into account so far)
    • added heuristic that gets a solution from other components and tries it (heur_trysol.?)
    • new trivial heuristic: tries zero solution, lower and upper bound solution and some variable lock based fixing
    • added new timing point, SCIP_HEURTIMING_DURINGPRICINGLOOP, for calling heuristics; If this timing point is used the corresponding heuristics is called during the pricing loop of variables; we also added this timing point to heur_simplerounding.{h,c} which has the effect that a LP solution which satisfies all integrality conditions during the pricing loop is detected
  • Interfaces:
    • added first version of an interface to NLP solvers (type_nlpi.h, struct_nlpi.h, nlpi.h, nlpi.c, nlpi_oracle.h, nlpi_oracle.c)
    • Preliminary support of non-convex MIQCPs: Constraint handler for quadratic constraints, NLP heuristic and Ipopt interface, see cons_quadratic.h.
    • There are LP-interfaces to QSopt and Gurobi (rudimentary).
  • Reader and Writer:
    • added reader and writer for FlatZinc models (reader_fzn.{c,h})
    • added writer for GAMS models (reader_gms.{c,h})

Performance improvements

Interface changes

  • A significant change for C++ users is that all include files of SCIP automatically detect C++ mode, i.e., no externC`` is needed anymore.
  • Reader for Flatzinc and GAMS models

New and changed callbacks

Deleted and changed API methods

  • SCIPcalcMIR() in scip.h has two new parameter mksetcoefsvalid and sol. The parameter mksetcoefsvalid stores whether the coefficients of the mixed knapsack set (mksetcoefs) computed in SCIPlpCalcMIR() are valid. If the mixed knapsack constraint obtained after aggregating LP rows is empty or contains too many nonzero elements the generation of the c-MIR cut is aborted in SCIPlpCalcMIR() and mksetcoefs is not valid. The input parameter sol can be used to separate a solution different from the LP solution.
  • new parameter set in SCIPconsSetInitial().
  • some interval arithmetic method take an additional argument to denote which value stands for infinity in an interval
  • Variables:
    • SCIPgetVarClosestVlb() and SCIPgetVarClosestVub() in scip.h have a new parameter sol. It can be used to obtain the closest variable bound w.r.t. a solution different from the LP solution.
    • new parameters lowerbound and result in type_pricer.h: lowerbound can save a lower bound computed by the pricer, result indicates whether the pricer guarantees that there exist no more variables if no variable was found

New API functions

Interfaces to external software

  • LP Interfaces:
    • heavily revised Mosek interface
    • new interface to QSopt due to Daniel Espinoza
    • First version of LP interfaces to Gurobi and QSopt
    • Major performance improvements in LP interfaces to Clp, Mosek and SoPlex
  • External Software:
    • adjusted interface to ZIMPL (reader_zpl.{c,h} for ZIMPL version 2.10; this interface should also work with older ZIMPL versions
    • Adjusted interface to Zimpl version 3.0.0
    • added first version of an interface to Ipopt (only QCP, no deletion of vars/cons allowed; nlpi_ipopt.(h|c))
  • SCIP Interfaces:

Changed parameters

  • removed parameter constraints/and/initiallp since it is not needed anymore;
  • set parameter constraints/and/sepafreq default value to 1
  • display character of oneopt heuristic changed to b

New parameters

  • branching/relpscost/advanced/conflenscore, default value 0.001
  • constraints/and/aggrlinearization in cons_and.c, aggregated version of the linearization
  • constraints/and/enforcecuts in cons_and.c, should cuts be separated during LP enforcing?
  • constraints/and/presolusehashing in cons_and.c, should pairwise presolving use hashing?, default TRUE
  • constraints/countsols/sollimit in cons_countsols.c, counting stops, if the given number of solutions were found (-1: no limit)
  • constraints/xor/presolusehashing in cons_xor.c, should pairwise presolving use hashing?, default TRUE
  • heuristics/oneopt/duringroot, default value TRUE

Build system

Makefile

  • extend Makefile to link against Ipopt if IPOPT=true is set

Fixed bugs

  • fixed wrong use of pointer in lp.c
  • fixed bug with array dimension not reset to zero when array is freed in pseudoobj propagator
  • fixed bug with enforcement of pseudo solutions: if pseudo solution is choosen because LP hit a limit, it has to be enforced in any case
  • fixed potential bug in coloring example: SCIPcreateChild() is now given an estimate in terms of the transformed problem by SCIPgetLocalTransEstimate(), no longer the estimated original problem value. Also clarified this in the comments for SCIPcreateChild()
  • fixed compiler warning warning: dereferencing type-punned pointer will break strict-aliasing rules which resuts in scip-crashes with gcc version 4.4.0
  • adjusted assert in var.c
  • fixed bug in SCIPvarGetActiveRepresentatives() in var.c
  • fixed bug with objective limit in lp.c: previously the infinity value of SCIP was used as default - now the value of LPI is used. In the earlier version in many cases the problems where never infeasible.
  • added and adjusted some asserts, initialized some values
  • increased the numerical stability of coefficient tightening for Big M formulations
  • fixed bug with incorrect pseudo activities when objective of a variable switches sign in linear constraint handler
  • fixed bug with empty constraints in several writing routines
  • fixed GGT-Kaibel-Bug in var.c, prop_pseudoobj.c and cons_varbound.c that occured while computing new values using infinity values
  • Bounds:
    • fixed bug in coefficient tightening with infinite bounds
    • fixed bug in solve.c: in case lowerbound >= upperbound, SCIPsolveIsStopped() returned SCIP_STATUS_GAPLIMIT
  • Nodes:
    • fixed bug in SCIPsolveNode() concerning the case that the time limit was hit while solving the LP relaxation of a subproblem which is already an LP (branching on pseudo solution is not possible)
    • fixed bug in vbc tools concerning of marking probing nodes
    • fixed bug in solve.c with nodes which are marked to be repropagated while enforcement
  • Variables:
    • fixed possible infinite loop while multiaggregating a variable in var.c
    • fixed bug in SCIPgetSolVals() similar to SCIPgetSolVal(): try to get original variables of transformed ones if the solution lives in original space
  • Pricing:
    • fixed potential bug: restarts are now only done if no active pricers exist
    • fixed bug in SCIPlpSolveAndEval(): if fastmip and pricers enabled and objlimit was reached but CPLEX did not perform the final pivot step in order to exceed the objlimit, do one additional simplex step with pricing strategy steepest edge, if this doesn't suffice, turn off fastmip temporarily and solve again. Also consider solstat of the new solution.
    • fixed bug with invalid pseudo solution (lower bound was always >= 0) when using pricing.
    • fixed bug in SCIPfreeProb() in scip.c: all pricers are deactivated now
  • Memory:
    • now frees debug memory
    • fixed bug with exponential complexity for reallocating memory in SCIPvarGetActiveRepresentatives() in var.c
    • fixed casting of void* pointers in memory.h for C++, adjusted the same for C in memory.h and due to that adjusted all header files(set whole files in extern C) and cpp-files(removed unnecessary extern C lines)
    • removed memory leak in connection with freeing branch and bound nodes: focusnode was not freed if both children could be cut off due to bounding
  • Reading and Writing:
    • corrected bug in reader_lp.c: earlier read bounds were thrown away (implementation was not conforming to standard)
    • fixed bug in reader_lp.c with respect to constraint and variable names which start with two or more dots ..
    • fixed bug in all readers w.r.t. SCIPgetProbvarLinearSum()
    • fixed bug in reader_mps.c with respect to corrupted files
    • fixed bug in reader_mps.c with respect to writing transformed problems
    • changed wrong writing of mps files due to constraints without any name
    • fixed a bug during reading debug solution file
    • fixed bug in case of reading an objective function in opb format with multiple occurrences of the same variable
    • fixed bug in case of reading an objective function in lp format with multiple occurrences of the same variable
    • fixed a wrong fix of a reading bug, which was in reality a writing bug in MPS format; integer variables in mps format without bounds are binary variables, if the bound of an integer variable is infinity you have to write this bound
  • Separation:
    • fixed bug in sepa_cmir.c, sepa_mcf.c and sepa_flowcover.c: sol different to LP solution is now separated
    • corrected two asserts in sepa_redcost.c (reduced costs can be negative for fixed variables: qsopt uses this)
    • fixed bug in sepa_zerohalf.c; replacement of own sorting functions by template functions was incorrect
    • fixed bug in var.c, cons_knapsack.c and sepa_flowcover.c: variable bounds corresponding to implication are not generated if coefficient is large, variable bounds with large coefficients are ignored for construction of knapsack and snf relaxations
    • fixed bug in sepa_impliedbound.c concerning redundant implications
  • Cuts:
    • fixed bug in sepa_cmir.c concerning uninitialized mksetcoefs (if MIR-cut generation is aborted because the aggregated constraint is empty or contains too many nonzero elements mksetcoefs is invalid)
    • interrupts optimization process if a node will be cutoff, which allows the solution
    • fixed bug in sepa_impliedbounds.c and sepa_intobj.c: if separating a sol, this sol is now also given to SCIPaddCut() so that the efficacy of the cut is now computed correctly
    • fixed bug in solve.c caused by integer overflow due to setting the number of cuts to INT_MAX
  • Presolving:
    • fixed wrong result in check.awk, if infeasible problems are stopped in presolving
    • fixed exponential calculation of solution values during check of original solution, therefore changed SCIPvarGetActiveRepresentatives() in var.c and flattened all multiaggregated vars at the end of presolving in exitPresolve()
    • fixed bug with wrong abort criterion in presolving
    • fixed bug in presol.c caused by not reseting presolver-wasdelayed status
    • fixed bug in SCIPconsSetInitial() that occurred in pairwise presolving: add or delete constraint in initconss when changing the initial flag
  • Constraints:
  • Knapsack Constraint Handler:
  • Linear Constraint Handler:
    • fixed infinity loop in simplify inequalities in cons_linear.c
    • fixed bug in cons_linear.c: do not select variable as slack variable for multiaggregation in convertLongEquality if it has been marked as not-multiaggregable
    • fixed bug in cons_linear.c: also do not multiaggregate variables in dual preproccessing if it has been marked as not-multiaggregable
    • fixed bug in cons_linear.c: slight decrease of epsilon in order to make sure that scaled coefficients are really integral
    • fixed bug in chgRhs() and chgLhs() of cons_linear.c: after changing lhs or rhs of a constraints lhs <= rhs has to be satisfied without numerical tolerances
  • Heuristics:
    • added and changed some SCIPisStopped() calls in several heuristics
    • fixed bug in oneopt heuritic with start solution which has become infeasible due to global bound changes
  • Interfaces:
    • corrected several bugs in the Clp-interface concerning return values
    • fixed potential interface bug: time limits of 0.0 are not anymore passed to the LP solver, which may have caused errors