[Help-glpk] One more question about how to use GLPK for specific problem

[Dmitriy Yun]

Hi Everyone,

I've found c# wrapper on GLPK, but don't know how to build code to use
the library for my specific problem.
Could you please help me to clarify sequence of steps required to make
it work properly?

The following is my problem.

1. There are N technicians and M customers.
2. Technicians should serve customers.
3. Technicians have restrictions on total working time (e.g. per week/year).
4. All customers should be served by one and only one technician. In
other words for one customer there is only one technician who serve
this customer.
5. The objective - to minimize the sum of working time of all technicians.

Input:
I. NxM matrix of weights (in my case - service times).
II. N vector of restrictions on technicians' total working time..

Output:
NxM adjacency matrix of {0, 1}

The problem complexity should be N^M.
Looks like I need Branch-and-Cut method to solve this problem.
--------------------------------------------------------------------------------------------------------------------------
Matrix of service times. Columns are customers, rows are technicians
7.30  10.80  13.00  2.70
9.30  9.00  13.00  8.50
5.30  9.00  9.00  12.50

Vector of technicians' total working time
10.00
18.30
14.20

Output adjacensy matrix should be like this
1  0  0  1
0  1  0  0
0  0  1  0

or in the equivalent form of { 0 1 2 0 }

I developed my own version of B-n-C algoriithm just for test version.
I wonna use GLKP version.
so for these data
solutions will be

 0  2  1  0 - 32
 0  1  2  0 - 28
 1  1  2  0 - 30
 0  1  2  1 - 33.8

Where the last number is the sum of technicians' working times.
The minimum solution is
0  1  2  0 - 28

So now I need to find it using GLKP.
--------------------------------------------------------------------------------------------------------------------------
I developed some code demonstrating how I understand this process, but
looks like it should be more sophisticated.

           LPProblem p = new LPProblem();
           p.ObjectiveDirection = OptimisationDirection.MINIMISE;

           p.AddRows(3);
           // the code below should be corrected definitely
           // here should be restriction on sum of working time  for
all customers served by technician
           p.SetRowBounds(1, BOUNDSTYPE.Upper, 0, 10.0f);  ???
           p.SetRowBounds(2, BOUNDSTYPE.Upper, 0, 18.3f);  ???
           p.SetRowBounds(3, BOUNDSTYPE.Upper, 0, 14.3f);  ???

           p.AddCols(4);

           // the code below should be corrected definitely -
           // here we should be sure that every customer served by
one and only one technician
           p.SetColBounds(1, BOUNDSTYPE.Lower, 1f, 1f);    ???
           p.SetColBounds(2, BOUNDSTYPE.Lower, 1f, 1f);    ???
           p.SetColBounds(3, BOUNDSTYPE.Lower, 1f, 1f);    ???
           p.SetColBounds(4, BOUNDSTYPE.Lower, 1f, 1f);    ???

           int[] a = new int[] { 0, 1, 2, 3 };
           p.SetMatRow(1, a, new double[] { 7.3f, 10.8f, 13.0f, 2.7f });
           p.SetMatRow(2, a, new double[] { 9.3f, 9.0f, 13.0f, 8.5f });
           p.SetMatRow(3, a, new double[] { 5.3f, 9.0f, 9.0f, 12.5f });

           new BnCCallback().SetCallback(p, new
BranchAndCutDelegate(delegate(BranchTree t, Object o) {
Console.Out.WriteLine("toto"); }));
           p.WriteSol("c:\\sol.txt");
--------------------------------------------------------------------------------------------------------------------------
-- 
With best regards,
Dmitry