1 /* asnlp.c (convert assignment problem to LP) */
2
3 /***********************************************************************
4 * This code is part of GLPK (GNU Linear Programming Kit).
5 * Copyright (C) 2009-2016 Free Software Foundation, Inc.
6 * Written by Andrew Makhorin <mao@gnu.org>.
7 *
8 * GLPK is free software: you can redistribute it and/or modify it
9 * under the terms of the GNU General Public License as published by
10 * the Free Software Foundation, either version 3 of the License, or
11 * (at your option) any later version.
12 *
13 * GLPK is distributed in the hope that it will be useful, but WITHOUT
14 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
15 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
16 * License for more details.
17 *
18 * You should have received a copy of the GNU General Public License
19 * along with GLPK. If not, see <http://www.gnu.org/licenses/>.
20 ***********************************************************************/
21
22 #include "env.h"
23 #include "glpk.h"
24
25 /***********************************************************************
26 * NAME
27 *
28 * glp_asnprob_lp - convert assignment problem to LP
29 *
30 * SYNOPSIS
31 *
32 * int glp_asnprob_lp(glp_prob *P, int form, glp_graph *G, int names,
33 * int v_set, int a_cost);
34 *
35 * DESCRIPTION
36 *
37 * The routine glp_asnprob_lp builds an LP problem, which corresponds
38 * to the assignment problem on the specified graph G.
39 *
40 * RETURNS
41 *
42 * If the LP problem has been successfully built, the routine returns
43 * zero, otherwise, non-zero. */
44
glp_asnprob_lp(glp_prob * P,int form,glp_graph * G,int names,int v_set,int a_cost)45 int glp_asnprob_lp(glp_prob *P, int form, glp_graph *G, int names,
46 int v_set, int a_cost)
47 { glp_vertex *v;
48 glp_arc *a;
49 int i, j, ret, ind[1+2];
50 double cost, val[1+2];
51 if (!(form == GLP_ASN_MIN || form == GLP_ASN_MAX ||
52 form == GLP_ASN_MMP))
53 xerror("glp_asnprob_lp: form = %d; invalid parameter\n",
54 form);
55 if (!(names == GLP_ON || names == GLP_OFF))
56 xerror("glp_asnprob_lp: names = %d; invalid parameter\n",
57 names);
58 if (v_set >= 0 && v_set > G->v_size - (int)sizeof(int))
59 xerror("glp_asnprob_lp: v_set = %d; invalid offset\n",
60 v_set);
61 if (a_cost >= 0 && a_cost > G->a_size - (int)sizeof(double))
62 xerror("glp_asnprob_lp: a_cost = %d; invalid offset\n",
63 a_cost);
64 ret = glp_check_asnprob(G, v_set);
65 if (ret != 0) goto done;
66 glp_erase_prob(P);
67 if (names) glp_set_prob_name(P, G->name);
68 glp_set_obj_dir(P, form == GLP_ASN_MIN ? GLP_MIN : GLP_MAX);
69 if (G->nv > 0) glp_add_rows(P, G->nv);
70 for (i = 1; i <= G->nv; i++)
71 { v = G->v[i];
72 if (names) glp_set_row_name(P, i, v->name);
73 glp_set_row_bnds(P, i, form == GLP_ASN_MMP ? GLP_UP : GLP_FX,
74 1.0, 1.0);
75 }
76 if (G->na > 0) glp_add_cols(P, G->na);
77 for (i = 1, j = 0; i <= G->nv; i++)
78 { v = G->v[i];
79 for (a = v->out; a != NULL; a = a->t_next)
80 { j++;
81 if (names)
82 { char name[50+1];
83 sprintf(name, "x[%d,%d]", a->tail->i, a->head->i);
84 xassert(strlen(name) < sizeof(name));
85 glp_set_col_name(P, j, name);
86 }
87 ind[1] = a->tail->i, val[1] = +1.0;
88 ind[2] = a->head->i, val[2] = +1.0;
89 glp_set_mat_col(P, j, 2, ind, val);
90 glp_set_col_bnds(P, j, GLP_DB, 0.0, 1.0);
91 if (a_cost >= 0)
92 memcpy(&cost, (char *)a->data + a_cost, sizeof(double));
93 else
94 cost = 1.0;
95 glp_set_obj_coef(P, j, cost);
96 }
97 }
98 xassert(j == G->na);
99 done: return ret;
100 }
101
102 /* eof */
103