Re: [Fwd: gmpl question]

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 <[email protected]> */

/* 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 <[email protected] 
> <mailto:[email protected]>> wrote:
>
>     -------- Forwarded Message --------
>     From: Davor Ocelic <[email protected] <mailto:[email protected]>>
>     To: [email protected] <mailto:[email protected]>
>     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 <http://twitter.com/fmardini>