Three testers for the MILPSolver module, each registered as a separate
ctest and built by the shared makefile.
-
test_cutschecks that a:MILPSolvercorrectly separates dynamic constraints viagenerate_dynamic_constraint(). It builds anNCoCubeBlock(the unit ball in the L1 norm, encoded with its exponentially many "crazy" constraints, separated trivially) and compares the repeatedly re-solved optimal value against the trivial optimization. The solver and its parameters are read fromMILPPar.txt; seebatch-cuts. -
test_batch_fixissues on one channel changes that name the same column more than once (aColVariablefixed and unfixed, the bound of aBoxConstraintchanged twice, the two mixed) and checks that every registered:MILPSolverends up with the last state, as it does when the same changes arrive one at a time. -
test_dualverifies that the dual solution returned by a:MILPSolverrespects the convention established byRowConstraint. The solver is configured byLPPar-dual.txt. -
test_farkasverifies that the certificate of infeasibility of each:MILPSolverofLPPar-farkas.txtthat the build has, with the parameters given there (HiGHS with the simplex method and with the interior point method, both of which have to give one), has on each row the sign of the optimal dual of the same row, has a positive value on a program with two-sided rows and bounds, and, with the homogeneous multipliers, does not depend on the Objective; and that the ray of an unbounded convex QP is a ray, with the parameters ofQPPar-farkas.txt. -
test_dynamicprovides comprehensive tests for anyCDASolverable to handle Linear Programs: it builds a random LP in anAbstractBlock, solves it with two attached solvers, then repeatedly modifies the LP (rows, variables, bounds, constants) and re-solves, comparing the results each time. The solvers are configured byLPPar-dynamic.txt; seebatch-dynamicandbatch-dynamic-L. -
test_reduced_costsverifies that the reduced costs become the duals of the bounds of the right Variable when the model has dynamic Variable in a Block that comes before the static ones, every registered:MILPSolversolving a small LP whose duals are known. -
test_stopped_boundsverifies that each:MILPSolverof the build, stopped by its time limit on a continuous problem, gives on the side of the optimum it has not proved an infinite or a valid bound, and not zero or a large finite number, and that once the time limit is lifted on the same Solver it solves the problem, with the optimal value as both bounds. -
test_free_rowsverifies that each:MILPSolverof the build solves again, warm and right, a small LP with rows free on both sides after a change of the coefficients of other rows, after rows are relaxed and enforced again, and after the free rows get a finite side and lose it, each value being also that of a Solver loaded from scratch. -
test_ipm_free_rowsverifies that the interior point of each:MILPSolverof the build that has one, without presolve, solves right a small LP with a free row followed by a row with two finite sides, and solves it again after the free row gets a finite side and loses it and after a row is relaxed and enforced again, and that the model it writes after the first solve is the one it writes before; the Solver and their options are those ofLPPar-ipm.txt. -
test_cutoff_statusverifies the cutoffs of each:MILPSolverof the build on a maximization and a minimization MIP with a constant in the objective: the cutoffs of theComputeConfigofMILPPar-cutoff.txt(an upper one, a lower one, both) have to survive loading the problem, the first solve has to stop (kCutOff, with the value of its solution beyond the cutoff and a valid bound) at a cutoff that the first solution reaches and to give the optimal value otherwise, and a second solve with a cutoff after a first one has to give either, and not throw. -
test_free_workspaceverifies that every:MILPSolverofLPPar-all.txtthat the build has, each of which may free after a solve the memory that its back-end keeps and the next solve does not need, gives the same status, value, primal values and duals as the others, across warm re-solves after changes of sides, bounds and costs, an infeasible solve and a solve with no change. -
test_partial_solutionverifies that each:MILPSolverof the build writes, with aSimpleConfiguration< std::vector< int > >given toget_var_solution()andget_dual_solution(), only the part of the solution of the sub-Blocks it lists (and of the Block itself for -1), dynamic rows and columns included, that any otherConfigurationgives the whole solution, and that an index of no sub-Block throws. -
test_qcp_dualverifies the duals that each:MILPSolverof the build solving a convex problem with quadratic rows writes in them, one with and one without a linear part, and in the linear rows that follow them, on a small problem whose multipliers are known; the:MILPSolverare those that take quadratic rows (LPPar-qcp.txt), CPLEX and Gurobi have to solve it, SCIP is skipped if it gives no duals of them. -
test_quad_row_modifyverifies that each:MILPSolverof the build that takes quadratic rows solves right a small problem with one of them after a change of its coefficients, of its right-hand side and of its Variable, against the same problem loaded anew. -
test_fail_feasverifies that a:MILPSolverwhose solver ends a MIP with a solution and no accuracy promise answerskLowPrecisionwith that solution:CPXMILPSolverwhen CPLEX stops the search for an error (CPXMIP_FAIL_FEAS,fail-feas.lpwithMILPCfg-fail-feas.txt), andGRBMILPSolverwhen Gurobi ends it as sub-optimal, keeping the bound of the search (grb-suboptimal.lpwithMILPCfg-grb-suboptimal.txt); both are the SOCP formulation of a delay-constrained routing problem. -
test_qpverifies what each:MILPSolverof the build does with small quadratic models whose optimum is known: a convex QP with a separable and a non-separable objective, minimized and (its opposite) maximized, with rows of every kind and finite and infinite bounds, whose value, solution and duals are checked (the duals through the stationarity of the KKT conditions too), an MIQP, and a sequence of Modifications of the QP (coefficients of the objective, a side, a row added and removed, a variable fixed), each solved again and compared with a fresh Solver; the QP is also solved withdblKKTTolon, every Solver having to pass the check, and a sloppyOSQPMILPSolverhaving to be caught by it. A Solver that is not meant to handle a model has to refuse it with an exception or an error status rather than answer.
Run a tester directly (for instance ./test_dynamic seed [...], pass no
argument to see its usage), or run a batch over a set of sizes and seeds.
The makefile builds test_cuts, test_dual, test_dynamic and
test_qp, including the MILPSolver module and all its dependencies, and
the core SMS++ library.
-
Antonio Frangioni
Dipartimento di Informatica
Università di Pisa -
Rafael Durbano Lobato
Dipartimento di Informatica
Università di Pisa -
Enrico Calandrini
Dipartimento di Informatica
Università di Pisa
This code is provided free of charge under the GNU Lesser General Public License version 3.0, see the LICENSE file for details.