1 | /* -*- C++ -*- |
---|
2 | * |
---|
3 | * This file is a part of LEMON, a generic C++ optimization library |
---|
4 | * |
---|
5 | * Copyright (C) 2003-2006 |
---|
6 | * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
---|
7 | * (Egervary Research Group on Combinatorial Optimization, EGRES). |
---|
8 | * |
---|
9 | * Permission to use, modify and distribute this software is granted |
---|
10 | * provided that this copyright notice appears in all copies. For |
---|
11 | * precise terms see the accompanying LICENSE file. |
---|
12 | * |
---|
13 | * This software is provided "AS IS" with no warranty of any kind, |
---|
14 | * express or implied, and with no claim as to its suitability for any |
---|
15 | * purpose. |
---|
16 | * |
---|
17 | */ |
---|
18 | |
---|
19 | /// \ingroup demos |
---|
20 | /// \file |
---|
21 | /// \brief A program demonstrating the LEMON LP solver interface |
---|
22 | /// |
---|
23 | /// This program is a simple application of the LEMON LP solver |
---|
24 | /// interface: we formulate a linear programming (LP) problem and then |
---|
25 | /// solve it using the underlying solver (GLPK or CPLEX for |
---|
26 | /// example). For the detailed documentation of the LEMON LP solver |
---|
27 | /// interface read \ref lemon::LpSolverBase "this". |
---|
28 | /// |
---|
29 | /// \include lp_demo.cc |
---|
30 | |
---|
31 | #include <lemon/lp.h> |
---|
32 | |
---|
33 | #include <iostream> |
---|
34 | |
---|
35 | using namespace lemon; |
---|
36 | |
---|
37 | int main() |
---|
38 | { |
---|
39 | //The following example is taken from the documentation of the GLPK library. |
---|
40 | //See it in the GLPK reference manual and among the GLPK sample files (sample.c) |
---|
41 | |
---|
42 | //A default solver is taken |
---|
43 | Lp lp; |
---|
44 | typedef Lp::Row Row; |
---|
45 | typedef Lp::Col Col; |
---|
46 | |
---|
47 | |
---|
48 | std::cout<<"A program demonstrating the LEMON LP solver interface"<<std::endl; |
---|
49 | std::cout<<"Solver used: "<<default_solver_name<<std::endl; |
---|
50 | |
---|
51 | //This will be a maximization |
---|
52 | lp.max(); |
---|
53 | |
---|
54 | //We add coloumns (variables) to our problem |
---|
55 | Col x1 = lp.addCol(); |
---|
56 | Col x2 = lp.addCol(); |
---|
57 | Col x3 = lp.addCol(); |
---|
58 | |
---|
59 | //Constraints |
---|
60 | lp.addRow(x1+x2+x3 <=100); |
---|
61 | lp.addRow(10*x1+4*x2+5*x3<=600); |
---|
62 | lp.addRow(2*x1+2*x2+6*x3<=300); |
---|
63 | //Nonnegativity of the variables |
---|
64 | lp.colLowerBound(x1, 0); |
---|
65 | lp.colLowerBound(x2, 0); |
---|
66 | lp.colLowerBound(x3, 0); |
---|
67 | //Objective function |
---|
68 | lp.obj(10*x1+6*x2+4*x3); |
---|
69 | |
---|
70 | //Call the routine of the underlying LP solver |
---|
71 | lp.solve(); |
---|
72 | |
---|
73 | //Print results |
---|
74 | if (lp.primalStatus()==LpSolverBase::OPTIMAL){ |
---|
75 | std::cout<<"Optimal solution found!"<<std::endl; |
---|
76 | printf("optimum value = %g; x1 = %g; x2 = %g; x3 = %g\n", |
---|
77 | lp.primalValue(), |
---|
78 | lp.primal(x1), lp.primal(x2), lp.primal(x3)); |
---|
79 | } |
---|
80 | else{ |
---|
81 | std::cout<<"Optimal solution not found!"<<std::endl; |
---|
82 | } |
---|
83 | |
---|
84 | //End of LEMON style code |
---|
85 | |
---|
86 | //Here comes the same problem written in C using GLPK API routines |
---|
87 | |
---|
88 | // LPX *lp; |
---|
89 | // int ia[1+1000], ja[1+1000]; |
---|
90 | // double ar[1+1000], Z, x1, x2, x3; |
---|
91 | // s1: lp = lpx_create_prob(); |
---|
92 | // s2: lpx_set_prob_name(lp, "sample"); |
---|
93 | // s3: lpx_set_obj_dir(lp, LPX_MAX); |
---|
94 | // s4: lpx_add_rows(lp, 3); |
---|
95 | // s5: lpx_set_row_name(lp, 1, "p"); |
---|
96 | // s6: lpx_set_row_bnds(lp, 1, LPX_UP, 0.0, 100.0); |
---|
97 | // s7: lpx_set_row_name(lp, 2, "q"); |
---|
98 | // s8: lpx_set_row_bnds(lp, 2, LPX_UP, 0.0, 600.0); |
---|
99 | // s9: lpx_set_row_name(lp, 3, "r"); |
---|
100 | // s10: lpx_set_row_bnds(lp, 3, LPX_UP, 0.0, 300.0); |
---|
101 | // s11: lpx_add_cols(lp, 3); |
---|
102 | // s12: lpx_set_col_name(lp, 1, "x1"); |
---|
103 | // s13: lpx_set_col_bnds(lp, 1, LPX_LO, 0.0, 0.0); |
---|
104 | // s14: lpx_set_obj_coef(lp, 1, 10.0); |
---|
105 | // s15: lpx_set_col_name(lp, 2, "x2"); |
---|
106 | // s16: lpx_set_col_bnds(lp, 2, LPX_LO, 0.0, 0.0); |
---|
107 | // s17: lpx_set_obj_coef(lp, 2, 6.0); |
---|
108 | // s18: lpx_set_col_name(lp, 3, "x3"); |
---|
109 | // s19: lpx_set_col_bnds(lp, 3, LPX_LO, 0.0, 0.0); |
---|
110 | // s20: lpx_set_obj_coef(lp, 3, 4.0); |
---|
111 | // s21: ia[1] = 1, ja[1] = 1, ar[1] = 1.0; /* a[1,1] = 1 */ |
---|
112 | // s22: ia[2] = 1, ja[2] = 2, ar[2] = 1.0; /* a[1,2] = 1 */ |
---|
113 | // s23: ia[3] = 1, ja[3] = 3, ar[3] = 1.0; /* a[1,3] = 1 */ |
---|
114 | // s24: ia[4] = 2, ja[4] = 1, ar[4] = 10.0; /* a[2,1] = 10 */ |
---|
115 | // s25: ia[5] = 3, ja[5] = 1, ar[5] = 2.0; /* a[3,1] = 2 */ |
---|
116 | // s26: ia[6] = 2, ja[6] = 2, ar[6] = 4.0; /* a[2,2] = 4 */ |
---|
117 | // s27: ia[7] = 3, ja[7] = 2, ar[7] = 2.0; /* a[3,2] = 2 */ |
---|
118 | // s28: ia[8] = 2, ja[8] = 3, ar[8] = 5.0; /* a[2,3] = 5 */ |
---|
119 | // s29: ia[9] = 3, ja[9] = 3, ar[9] = 6.0; /* a[3,3] = 6 */ |
---|
120 | // s30: lpx_load_matrix(lp, 9, ia, ja, ar); |
---|
121 | // s31: lpx_simplex(lp); |
---|
122 | // s32: Z = lpx_get_obj_val(lp); |
---|
123 | // s33: x1 = lpx_get_col_prim(lp, 1); |
---|
124 | // s34: x2 = lpx_get_col_prim(lp, 2); |
---|
125 | // s35: x3 = lpx_get_col_prim(lp, 3); |
---|
126 | // s36: printf("\nZ = %g; x1 = %g; x2 = %g; x3 = %g\n", Z, x1, x2, x3); |
---|
127 | // s37: lpx_delete_prob(lp); |
---|
128 | // return 0; |
---|
129 | |
---|
130 | return 0; |
---|
131 | } |
---|