This web page distributes small software examples, mostly (but not exclusively) in C++, and the accompanying data, to illustrate the main issues regarding the (practical, software) development of Decision Support Systems (DSS) based on mathematical models.
In order to use these programs it may be necessary to download open-source optimization solvers from the web pages of the corresponding projects, such as MCFClass or COIN OR. All the codes are written to be as portable as possible (file/console input and output) and are provided with simple Unix makefiles; adapting them to other operating systems should be easy.
We distribute material pertaining to the following optimization problems:
For this easy variant of location problem we distribute:
a small collection of instances, "artificial" ones or taken from well-known repositories (see readme.txt).
a few spreadsheets in OpenOffice or Microsoft Excel for the solution of small CWL instances (among the above ones) with the resident optimization solvers of these programs. A version of an instance with an added nonlinear term in the cost function is provided to show how dramatic an impact this has on the ability to solve it. A large instance is also provided to show that solving time indeed grows unduly large with size. Finally, a small utility is provided to help turning .txt instances into spreadsheets (but a lot of the work still has to be done by hand).
a small C++ code that solves the continuous relaxation of the problem by reformulating it as a Min-Cost Flow problem and using a MCFClass solver. A quick and dirty rounding heuristic is also employed to build a feasible solution for the problem where the design variables only must be integer, and it is extended to an inerative slope scaling heuristic which tries to improve the quality of the obtained integer solution by appropriately scaling the costs of the "warehouse arcs".
a small C++ code for solving CWL instances (both in the splittable and unsplittable version) using a OsiSolverInterface object (provisions in the code for CBC and Cplex). The coefficient matrix of the model is constructed row- and colum-wise with calls to the relevant methods (addRow() e addCol()), either directly on the solver object or on an intermediate CoinModel object. Options are provided for outputting the model on file, possibly with "nice names" for rows and columns.
a small C++ code for solving CWL instances (both in the splittable and unsplittable version) using a OsiSolverInterface object (provisions in the code for CBC and Cplex). The model is constructed with FlopC++.
a small .m function for solving CWL instances using the YALMIP modeling system under Matlab. The function can create a random convex separable quadratic component in the objective function, just to show that (convex) MIQPs can be solved with comparable accuracy than MILP (it's convexity, not linearity, that makes all the difference).
a small C++ file for solving CWL instances using Cplex. The model is constructed through calls to the relevant functions of the C API. A simple cutcallback function is implemented which dynamically adds strong linking constraints to improve the continuous relaxation bound.
a small C++ file for solving the Lagrangian Dual of CWL (the "right one", that with knapsack-like subproblems) through a Cutting Plane algorithm (Dantzig-Wolfe decomposition), either in aggregated or disaggregated version and with a "phase 0". The subproblems are solved with a OsiCbcSolverInterface in the unsplittable case (binary knapsack) or via the standard greedy approach in the splittable case (continuous knapsack). For the splittable case, the "convexified" primal solution (as opposed to the solution of the continuous relaxation) is used as the basis for the trivial rounding heuristic.
a small C++ file for solving the (right ...) Lagrangian Dual of CWL, with subproblems as above, with a "home-made" subgradient algoritm. The continuous relaxation is solved with a OsiClpSolverInterface to provide both a feasible solution (in the splittable case) and a starting point for the subgradient algorithm.
a small C++ file for solving the same Lagrangian Dual as above with a(n aggregated proximal) Bundle algorithm with quadratic stabilization, employing a specialized Quadratic Programming master problem solver. The rounding heuristic uses the available "convexified" primal solution, but also re-computes the flow component (both in the splittable and unsplittable case) via an OsiSolverInterface (using CBC).
A small set of largish LPs (with upwards to 105 variables) in .lp format to test the effectiveness of different LP algorithms (primal and dual simplex, barrier). Some of them are strongly network-structured, being Multicommodity Flow or Network Design problems, and therefore very sparse. Others are taken from the MIPLIB 2010 collection of Mixed-Integer LPs (but integrality of variables is removed). Warning: about 54 Mb (few problems, but largish ones).
For this "easy difficult" combinatorial optimization problem we distribute:
kcover: Separation of cover inequalities, in order to show its impact on the upper bound produced by the continuous relaxation. Both exact separtion (using a OsiCbcSolverInterface) and heuristic separation (using a Greedy CUD aproach plus possibly a 2-swap local search) are implemented in order to explore the trade-offs between the separation time and the quality of the obtained upper bounds.
kdp: solution of the problem (with integer data) via the classical pseudo-polynomial Dynamic Programming algorithm based on the longest path pseudo-polynomial reformulation of the problem; the effectiveness is compared with that of a general-purpose MILP solver (CBC, through a OsiCbcSolverInterface) on randomly-generated instances.
For this standard packing problem we distribute:
a small collection of instances, either artificial or taken by the main repositories (see readme.txt).
kant: solving (...) the Kantorovich formulation using a OsiSolver, either CBC (!?! good luck with that!) or Cplex, with the model constructed by FlopCpp. It includes activating/disactivating cuts and symmetry breaking techniques (either implicit or explicit) that sometimes have some impact. It also includes a very simple, yet very effective, LPT heuristic to find an initial solution and therefore a decent bound for constructing the model.
gg: heuristically solving Cutting Stock problems using a column generation approach based on the Gilmore & Gomory model. Column generation is only done at root node to derive a (good) lower bound and the corresponding set of columns, then the problem is frozen and solved to optimality with a OsiCbcSolver.