COIN-OR::LEMON - Graph Library

Changeset 55:edb7d5759e0d in lemon-tutorial

03/01/10 02:27:36 (14 years ago)
Peter Kovacs <kpeter@…>

Greatly extend LP section

2 edited


  • lp.dox

    r50 r55  
    4545quite easily.
    47 In this section, we will show two examples. The first one shows how simple
    48 it is to formalize and solve an LP problem in LEMON, while the second one
    49 shows how LEMON facilitates solving network optimization problems using LP
    50 solvers.
    52 \code
    53   Lp lp;
    55   Lp::Col x1 = lp.addCol();
    56   Lp::Col x2 = lp.addCol();
    58   lp.addRow(0 <= x1 + x2 <= 100);
    59   lp.addRow(2 * x1 <= x2 + 32);
    61   lp.colLowerBound(x1, 0);
    62   lp.colUpperBound(x2, 100);
    64   lp.max();
    65   lp.obj(10 * x1 + 6 * x2);
    66   lp.solve();
    68   std::cout << "Objective function value: " << lp.primal() << std::endl;
    69   std::cout << "x1 = " << lp.primal(x1) << std::endl;
    70   std::cout << "x2 = " << lp.primal(x2) << std::endl;
    71 \endcode
    73 \ref LpBase::Col "Lp::Col" type represents the variables in the LP problems,
    74 while \ref LpBase::Row "Lp::Row" represents the constraints. The numerical
    75 operators can be used to form expressions from columns and dual
    76 expressions from rows. Due to the suitable operator overloads,
    77 a problem can be described in C++ conveniently, directly as it is
     47[SEC]sec_lp_basics[SEC] Basic LP Features
     49The following example demonstrates how simple it is to formalize and solve
     50an LP problem in LEMON. You can find the whole program in \ref
     53\skip Create
     54\until }
     55\until }
     57\ref LpBase::Col "Lp::Col" type represents the columns, i.e. the (primal)
     58variables of the LP problem. The numerical operators can be used to form
     59expressions from columns, which are required for specifying rows
     60(constraints) and the objective function. Due to the suitable operator
     61overloads, a problem can be described in C++ conveniently, directly as it is
    7862expressed in mathematics.
     63After specifying all the parameters of the problem, we can solve it using
     64the \ref LpSolver::solve() "solve()" function. The status of the solution
     65(namely OPTIMAL, UNBOUNDED, INFEASIBLE etc.) can be obtained using
     66\ref LpSolver::primalType() "primalType()" and the results can be
     67obtained using \ref LpSolver::primal() "primal()".
     69The above problem has an optimal solution. If you execute this example,
     70it will print out the following results.
     73  Objective function value: 67.5
     74  x1 = 7.5
     75  x2 = 10
     78However, if you, for example, removed the lines that specify the rows,
     79you would obtain an LP problem, for which the objective function value
     80is unbounded over the feasible solutions. Thus the program would print
     81out this line.
     84  Optimal solution found.
     87If you would like to build linear expressions or constraints in more steps,
     88then you can use the classes \ref LpBase::Expr "Lp::Expr" and
     89\ref LpBase::Constr "Lp::Constr". For example, this line
     91  lp.addRow(x1 - 5 <= x2);
     93can also be written as
     95  Lp::Expr e1, e2;
     96  e1 = x1;
     97  e1 -= 5;
     98  e2 = x2;
     99  Lp::Constr c = e1 <= e2;
     100  lp.addRow(c);
     103These classes make it easy to build more complex expressions and constraints,
     104e.g. using loops. For example, we can sum all the variables (columns) in an
     105expression using the \ref LpBase::ColIt "Lp::ColIt" iterator, which can be
     106used the same as node and arc iterators for graphs.
     109  Lp::Expr sum;
     110  for (Lp::ColIt col(lp); col != INVALID; ++col) {
     111    sum += col;
     112  }
     115After solving the problem, you can query the value of any primal expression,
     116not just the individual columns and the objective function.
     118\todo Check this example after closing ticket #326.
     121  std::cout << lp.primal(sum) << std::endl;
     124Of course, working with the dual problem is also supported by the LP
     125interface. \ref LpBase::Row "Lp::Row" represents the rows, i.e. the dual
     126variables of the LP problem.
     129  Lp::Row r = lp.addRow(x2 >= 3);
     132The dual solutions of an LP problem can be obtained using the functions
     133\ref LpSolver::dualType() "dualType()" and \ref LpSolver::dual "dual()"
     134(after solving the problem).
     137  std::cout << lp.dual(r) << std::endl;
     140\ref LpBase::DualExpr "Lp::DualExpr" can be used to build dual expressions
     141from rows and \ref LpBase::RowIt "Lp::RowIt" can be used to list the rows.
     144  Lp::DualExpr dual_sum;
     145  for (Lp::RowIt row(lp); row != INVALID; ++row) {
     146    dual_sum += row;
     147  }
     150The LP solver interface provides several other features, which are
     151documented in the classes \ref LpBase and \ref LpSolver.
     152For detailed documentation, see these classes in the reference manual.
     154If you would like to use a specific solver instead of the default one,
     155you can use \ref GlpkLp, \ref ClpLp, \ref CplexLp etc. instead of
     156the class \ref Lp.
     159[SEC]sec_lp_mip[SEC] Mixed Integer Programming
     161LEMON also provides a similar high-level interface for mixed integer
     162programming (MIP) solvers. The default MIP solver can be used through
     163the class \ref Mip, while the concrete solvers are implemented in the
     164classes \ref GlpkMip, \ref CbcMip, \ref CplexMip etc.
     166The following example demonstrates the usage of the MIP solver interface.
     167The whole program can be found in \ref
     170\skip Create
     171\until }
     172\until }
     174\todo Check this demo file after closing ticket #326.
     175E.g. could we write <tt>mip.sol()</tt> instead of <tt>mip.solValue()</tt>?
     176Or could we write <tt>primalValue()</tt> for \c Lp in \c
     178In this program, the same problem is built as in the above example,
     179with the exception that the variable \c x1 is specified to be
     180\c INTEGER valued. \c x2 is set to \c REAL, which is the default option.
     183  // Set the type of the columns
     184  mip.colType(x1, Mip::INTEGER);
     185  mip.colType(x2, Mip::REAL);
     188Because of this integrality requirement, the results will be different
     189from the LP solution.
     192  Objective function value: 67
     193  x1 = 8
     194  x2 = 9
     197The documnetation of the MIP solver interface can be found in the
     198reference manual at the class \ref MipSolver. The common parts of the
     199LP and MIP interfaces are docmented in their common ancestor class
     200\ref LpBase.
     203[SEC]sec_lp_optimization[SEC] Solving Complex Optimization Problems
     205The LP and MIP solvers are powerful tools for solving various complex
     206optimization problems, as well.
    80207The following example solves a maximum flow problem with linear
    81 programming. Several other graph optimization problems can also be
    82 expressed as linear programs and this interface helps to solve them easily
    83 (though usually not so efficiently as by a direct combinatorial method).
    85 \code
    86   Lp lp;
    87   ListDigraph::ArcMap<Lp::Col> f(g);
    88   lp.addColSet(f);
    90   // Capacity constraints
    91   for (ListDigraph::ArcIt a(g); a != INVALID; ++a) {
    92     lp.colLowerBound(f[a], 0);
    93     lp.colUpperBound(f[a], capacity[a]);
    94   }
    96   // Flow conservation constraints
    97   for (ListDigraph::NodeIt n(g); n != INVALID; ++n) {
    98     if (n == src || n == trg) continue;
    99     Lp::Expr e;
    100     for (ListDigraph::OutArcIt a(g,n); a != INVALID; ++a) e += f[a];
    101     for (ListDigraph::InArcIt a(g,n); a != INVALID; ++a) e -= f[a];
    102     lp.addRow(e == 0);
    103   }
    105   // Objective function
    106   Lp::Expr o;
    107   for (ListDigraph::OutArcIt a(g,src); a != INVALID; ++a) o += f[a];
    108   for (ListDigraph::InArcIt a(g,src); a != INVALID; ++a) o -= f[a];
    110   lp.max();
    111   lp.obj(o);
    112   lp.solve();
    114   std::cout << "Max flow value: " << lp.primal() << std::endl;
    115 \endcode
     208programming, see the whole program in \re
     209Several other graph optimization problems can also be expressed as
     210linear programs and the interface provided in LEMON facilitates solving
     211them easily (though usually not so efficiently as by a direct
     212combinatorial method, if one exists).
     215\skip DIGRAPH_TYPEDEFS
     216\until solve()
     218\note This problem can be solved much more efficiently using common
     219combinatorial optimization methods, such as the \ref Preflow
     220"preflow push-relabel algorithm".
  • toc.txt

    r46 r55  
    3434** sec_other_adaptors
    3535* sec_lp
     36** sec_lp_basics
     37** sec_lp_mip
     38** sec_lp_optimization
    3639* sec_lgf
    3740* sec_tools
Note: See TracChangeset for help on using the changeset viewer.