1.1 --- a/demo/hello_lemon.cc Sun Feb 28 19:38:57 2010 +0100
1.2 +++ b/demo/hello_lemon.cc Mon Mar 01 02:26:24 2010 +0100
1.3 @@ -20,6 +20,7 @@
1.4 ///\brief Simple "Hello World!" program for LEMON.
1.5 ///
1.6 /// Simple "Hello World!" program for LEMON.
1.7 +///
1.8 /// \include hello_lemon.cc
1.9
1.10 #include <iostream>
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/demo/lp_demo.cc Mon Mar 01 02:26:24 2010 +0100
2.3 @@ -0,0 +1,68 @@
2.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
2.5 + *
2.6 + * This file is a part of LEMON, a generic C++ optimization library.
2.7 + *
2.8 + * Copyright (C) 2003-2010
2.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
2.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
2.11 + *
2.12 + * Permission to use, modify and distribute this software is granted
2.13 + * provided that this copyright notice appears in all copies. For
2.14 + * precise terms see the accompanying LICENSE file.
2.15 + *
2.16 + * This software is provided "AS IS" with no warranty of any kind,
2.17 + * express or implied, and with no claim as to its suitability for any
2.18 + * purpose.
2.19 + *
2.20 + */
2.21 +
2.22 +///\file
2.23 +///\brief Demo program for the LP solver interface.
2.24 +///
2.25 +/// This demo program shows how the LEMON LP solver interface can be used.
2.26 +/// A simple linear programming (LP) problem is formulated and solved using
2.27 +/// the default LP solver (e.g. GLPK).
2.28 +///
2.29 +/// \include lp_demo.cc
2.30 +
2.31 +#include <iostream>
2.32 +#include <lemon/lp.h>
2.33 +
2.34 +using namespace lemon;
2.35 +
2.36 +int main()
2.37 +{
2.38 + // Create an instance of the default LP solver class
2.39 + // (it will represent an "empty" problem at first)
2.40 + Lp lp;
2.41 +
2.42 + // Add two columns (variables) to the problem
2.43 + Lp::Col x1 = lp.addCol();
2.44 + Lp::Col x2 = lp.addCol();
2.45 +
2.46 + // Add rows (constraints) to the problem
2.47 + lp.addRow(x1 - 5 <= x2);
2.48 + lp.addRow(0 <= 2 * x1 + x2 <= 25);
2.49 +
2.50 + // Set lower and upper bounds for the columns (variables)
2.51 + lp.colLowerBound(x1, 0);
2.52 + lp.colUpperBound(x2, 10);
2.53 +
2.54 + // Specify the objective function
2.55 + lp.max();
2.56 + lp.obj(5 * x1 + 3 * x2);
2.57 +
2.58 + // Solve the problem using the underlying LP solver
2.59 + lp.solve();
2.60 +
2.61 + // Print the results
2.62 + if (lp.primalType() == Lp::OPTIMAL) {
2.63 + std::cout << "Objective function value: " << lp.primal() << std::endl;
2.64 + std::cout << "x1 = " << lp.primal(x1) << std::endl;
2.65 + std::cout << "x2 = " << lp.primal(x2) << std::endl;
2.66 + } else {
2.67 + std::cout << "Optimal solution not found." << std::endl;
2.68 + }
2.69 +
2.70 + return 0;
2.71 +}
3.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
3.2 +++ b/demo/lp_maxflow_demo.cc Mon Mar 01 02:26:24 2010 +0100
3.3 @@ -0,0 +1,105 @@
3.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
3.5 + *
3.6 + * This file is a part of LEMON, a generic C++ optimization library.
3.7 + *
3.8 + * Copyright (C) 2003-2010
3.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
3.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
3.11 + *
3.12 + * Permission to use, modify and distribute this software is granted
3.13 + * provided that this copyright notice appears in all copies. For
3.14 + * precise terms see the accompanying LICENSE file.
3.15 + *
3.16 + * This software is provided "AS IS" with no warranty of any kind,
3.17 + * express or implied, and with no claim as to its suitability for any
3.18 + * purpose.
3.19 + *
3.20 + */
3.21 +
3.22 +///\file
3.23 +///\brief Demo program that solves maximum flow problems using the LP interface
3.24 +///
3.25 +/// This demo program shows how to solve the maximum flow problem using
3.26 +/// the LEMON LP solver interface. We would like to lay the emphasis on the
3.27 +/// simplicity of the way one can formulate LP constraints that arise in graph
3.28 +/// theory using LEMON.
3.29 +///
3.30 +/// \include lp_maxflow_demo.cc
3.31 +
3.32 +#include <iostream>
3.33 +#include <lemon/smart_graph.h>
3.34 +#include <lemon/lgf_reader.h>
3.35 +#include <lemon/lp.h>
3.36 +
3.37 +using namespace lemon;
3.38 +
3.39 +template <typename GR, typename CAP>
3.40 +double maxFlow(const GR &g, const CAP &capacity,
3.41 + typename GR::Node source, typename GR::Node target)
3.42 +{
3.43 + TEMPLATE_DIGRAPH_TYPEDEFS(GR);
3.44 +
3.45 + // Create an instance of the default LP solver
3.46 + Lp lp;
3.47 +
3.48 + // Add a column to the problem for each arc
3.49 + typename GR::template ArcMap<Lp::Col> f(g);
3.50 + lp.addColSet(f);
3.51 +
3.52 + // Capacity constraints
3.53 + for (ArcIt a(g); a != INVALID; ++a) {
3.54 + lp.colLowerBound(f[a], 0);
3.55 + lp.colUpperBound(f[a], capacity[a]);
3.56 + }
3.57 +
3.58 + // Flow conservation constraints
3.59 + for (NodeIt n(g); n != INVALID; ++n) {
3.60 + if (n == source || n == target) continue;
3.61 + Lp::Expr e;
3.62 + for (OutArcIt a(g, n); a != INVALID; ++a) e += f[a];
3.63 + for (InArcIt a(g, n); a != INVALID; ++a) e -= f[a];
3.64 + lp.addRow(e == 0);
3.65 + }
3.66 +
3.67 + // Objective function
3.68 + Lp::Expr o;
3.69 + for (OutArcIt a(g, source); a != INVALID; ++a) o += f[a];
3.70 + for (InArcIt a(g, source); a != INVALID; ++a) o -= f[a];
3.71 + lp.max();
3.72 + lp.obj(o);
3.73 +
3.74 + // Solve the LP problem
3.75 + lp.solve();
3.76 +
3.77 + return lp.primal();
3.78 +}
3.79 +
3.80 +
3.81 +int main(int argc, char *argv[])
3.82 +{
3.83 + // Check the arguments
3.84 + if (argc < 2) {
3.85 + std::cerr << "Usage:" << std::endl;
3.86 + std::cerr << " lp_maxflow_demo <input_file>" << std::endl;
3.87 + std::cerr << "The given input file has to contain a maximum flow\n"
3.88 + << "problem in LGF format (like 'maxflow.lgf')."
3.89 + << std::endl;
3.90 + return 0;
3.91 + }
3.92 +
3.93 + // Read the input file
3.94 + SmartDigraph g;
3.95 + SmartDigraph::ArcMap<double> cap(g);
3.96 + SmartDigraph::Node s, t;
3.97 +
3.98 + digraphReader(g, argv[1])
3.99 + .arcMap("capacity", cap)
3.100 + .node("source", s)
3.101 + .node("target", t)
3.102 + .run();
3.103 +
3.104 + // Solve the problem and print the result
3.105 + std::cout << "Max flow value: " << maxFlow(g, cap, s, t) << std::endl;
3.106 +
3.107 + return 0;
3.108 +}
4.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
4.2 +++ b/demo/maxflow.lgf Mon Mar 01 02:26:24 2010 +0100
4.3 @@ -0,0 +1,34 @@
4.4 +@nodes
4.5 +label
4.6 +0
4.7 +1
4.8 +2
4.9 +3
4.10 +4
4.11 +5
4.12 +6
4.13 +7
4.14 +8
4.15 +9
4.16 +@arcs
4.17 + capacity
4.18 +0 1 20
4.19 +0 2 0
4.20 +1 1 3
4.21 +1 2 8
4.22 +1 3 8
4.23 +2 5 5
4.24 +3 2 5
4.25 +3 5 5
4.26 +3 6 5
4.27 +4 3 3
4.28 +5 7 3
4.29 +5 6 10
4.30 +5 8 10
4.31 +6 8 8
4.32 +8 9 20
4.33 +8 1 5
4.34 +9 5 5
4.35 +@attributes
4.36 +source 1
4.37 +target 8
5.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
5.2 +++ b/demo/mip_demo.cc Mon Mar 01 02:26:24 2010 +0100
5.3 @@ -0,0 +1,72 @@
5.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
5.5 + *
5.6 + * This file is a part of LEMON, a generic C++ optimization library.
5.7 + *
5.8 + * Copyright (C) 2003-2010
5.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
5.11 + *
5.12 + * Permission to use, modify and distribute this software is granted
5.13 + * provided that this copyright notice appears in all copies. For
5.14 + * precise terms see the accompanying LICENSE file.
5.15 + *
5.16 + * This software is provided "AS IS" with no warranty of any kind,
5.17 + * express or implied, and with no claim as to its suitability for any
5.18 + * purpose.
5.19 + *
5.20 + */
5.21 +
5.22 +///\file
5.23 +///\brief Demo program for the MIP solver interface.
5.24 +///
5.25 +/// This demo program shows how the LEMON MIP solver interface can be used.
5.26 +/// A simple mixed integer programming (MIP) problem is formulated and solved
5.27 +/// using the default MIP solver (e.g. GLPK).
5.28 +///
5.29 +/// \include mip_demo.cc
5.30 +
5.31 +#include <iostream>
5.32 +#include <lemon/lp.h>
5.33 +
5.34 +using namespace lemon;
5.35 +
5.36 +int main()
5.37 +{
5.38 + // Create an instance of the default MIP solver class
5.39 + // (it will represent an "empty" problem at first)
5.40 + Mip mip;
5.41 +
5.42 + // Add two columns (variables) to the problem
5.43 + Mip::Col x1 = mip.addCol();
5.44 + Mip::Col x2 = mip.addCol();
5.45 +
5.46 + // Add rows (constraints) to the problem
5.47 + mip.addRow(x1 - 5 <= x2);
5.48 + mip.addRow(0 <= 2 * x1 + x2 <= 25);
5.49 +
5.50 + // Set lower and upper bounds for the columns (variables)
5.51 + mip.colLowerBound(x1, 0);
5.52 + mip.colUpperBound(x2, 10);
5.53 +
5.54 + // Set the type of the columns
5.55 + mip.colType(x1, Mip::INTEGER);
5.56 + mip.colType(x2, Mip::REAL);
5.57 +
5.58 + // Specify the objective function
5.59 + mip.max();
5.60 + mip.obj(5 * x1 + 3 * x2);
5.61 +
5.62 + // Solve the problem using the underlying MIP solver
5.63 + mip.solve();
5.64 +
5.65 + // Print the results
5.66 + if (mip.type() == Mip::OPTIMAL) {
5.67 + std::cout << "Objective function value: " << mip.solValue() << std::endl;
5.68 + std::cout << "x1 = " << mip.sol(x1) << std::endl;
5.69 + std::cout << "x2 = " << mip.sol(x2) << std::endl;
5.70 + } else {
5.71 + std::cout << "Optimal solution not found." << std::endl;
5.72 + }
5.73 +
5.74 + return 0;
5.75 +}