Re: [Fwd: gmpl question]

[Domingo Alvarez Duarte]

Hello Davor !

Based on your description and hints from Fouad maybe this does what you expect (you can try it online at https://meimporta.eu/myglpk-ext/):

====

/* ASSIGN, Assignment Problem */

/* Written in GNU MathProg by Andrew Makhorin <mao@gnu.org> */

/* The assignment problem is one of the fundamental combinatorial
   optimization problems.

   In its most general form, the problem is as follows:

   There are a number of agents and a number of tasks. Any agent can be
   assigned to perform any task, incurring some cost that may vary
   depending on the agent-task assignment. It is required to perform all
   tasks by assigning exactly one agent to each task in such a way that
   the total cost of the assignment is minimized.

   (From Wikipedia, the free encyclopedia.) */

param m, integer, > 0;
/* number of agents */

param n, integer, > 0;
/* number of tasks */

set I := 1..m;
/* set of agents */

set J := 1..n;
/* set of tasks */

param c{i in I, j in J}, >= 0;
/* cost of allocating task j to agent i */

var x{i in I, j in J}, >= 0;
/* x[i,j] = 1 means task j is assigned to agent i
   note that variables x[i,j] are binary, however, there is no need to
   declare them so due to the totally unimodular constraint matrix */

s.t. phi{i in I}: sum{j in J} x[i,j] <= n;
/* each agent can perform at most one task */

s.t. psi{j in J}: sum{i in I} x[i,j] = 1;
/* each task must be assigned exactly to one agent */

minimize obj: sum{i in I, j in J} c[i,j] * x[i,j];
/* the objective is to find a cheapest assignment */

solve;

printf "\n";
printf "Agent  Task       Cost\n";
printf "      ";
printf{j in J} "%5d ", j;
printf "\n";
for{i in I} {
  printf "%5d ", i;
  printf{j in J} "%5d ", x[i,j];
  printf "%10g\n", sum{j in J} c[i,j] * x[i,j];
  printf "\n";
}
printf "----------------------\n";
printf "     Total: %10g\n", sum{i in I, j in J} c[i,j] * x[i,j];
printf "\n";

data;

/* These data correspond to an example from [Christofides]. */

/* Optimal solution is 76 */

param m := 4;

param n := 8;

param c : 1  2  3  4  5  6  7  8 :=
      1  13 21 20 12  8 26 22 11
      2  12 36 25 41 40 11  4  8
      3  35 32 13 36 26 21 13 37
      4  34 54  7  8 12 22 11 40 ;

end;

====

Output:

====

GLPSOL: GLPK LP/MIP Solver, v4.65-ex, glp_double size 8
Parameter(s) specified in the command line:
 --math input_file
Reading model section from input_file...
80 lines were read
80 lines were read
Generating phi...
Generating psi...
Generating obj...
Model has been successfully generated
GLPK Simplex Optimizer, v4.65-ex
13 rows, 32 columns, 96 non-zeros
Preprocessing...
12 rows, 32 columns, 64 non-zeros
Scaling...
 A: min|aij| =  1.000e+00  max|aij| =  1.000e+00  ratio =  1.000e+00
Problem data seem to be well scaled
Constructing initial basis...
Size of triangular part is 12
*     0: obj =   1.880000000e+02 inf =   0.000e+00 (12)
*     6: obj =   7.900000000e+01 inf =   0.000e+00 (0)
OPTIMAL LP SOLUTION FOUND
Time used:   0.0 secs
Memory used: 0.1 Mb (128934 bytes)

Agent  Task       Cost
          1     2     3     4     5     6     7     8
    1     0     1     0     0     1     0     0     0         29

    2     1     0     0     0     0     1     1     1         35

    3     0     0     0     0     0     0     0     0          0

    4     0     0     1     1     0     0     0     0         15

----------------------
     Total:         79

Model has been successfully processed

====

Cheers !

On 17/12/21 18:53, Fouad Mardini wrote:

Hi,

Maybe add multiple variables per agent and limit their sum to the max per agent 

On Fri, 17 Dec 2021 at 17:31, Andrew Makhorin <mao@gnu.org> wrote:

-------- Forwarded Message --------
From: Davor Ocelic <docelic@hcoop.net>
To: mao@gnu.org
Subject: gmpl question
Date: Fri, 17 Dec 2021 10:07:38 +0100

Heya,

I would appreciate minimal help with gmpl if you could:

In the glpk example `assign.mod`, the constraint is that
an agent can have only one task assigned:

s.t. phi{i in I}: sum{j in J} x[i,j] <= 1;
/* each agent can perform at most one task */

I would need to change this rule so that an agent doesn't
have a limit on number of tasks, but all tasks need to be
distributed among a limited number of agents. (For example,
distribute the 8 tasks in the example to 4 agents).

Could you help me with the syntax for that?

Thank you kindly,
Davor

--

--
twitter.com/fmardini