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

[glpk xypron]

Hello Dimitry,

GLPK comes with a standalone solver GLPSOL which can import data
from CSV files or an SQL database.

Using the glpk library is only necessary, if you want to apply
heuristics like column generation or if you want to integrate
glpk into a larger application.

I suggest that you first formulate your problem with GMPL and
solve it with GLPSOL. This way you will be sure which equations
you want to create in the C# code.

---

Unfortunately you did not provide any information on the C#
wrapper you want to use.

Do you refer to GLPK#?
http://yoyovicks.blog.free.fr/

It comes with an example file in
GlpkSharp-src.7z\GlpkSharp\GlpkSharp\TestGlpkSharp\Program.cs

Look into directory
GlpkSharp-src.7z\GlpkSharp\GlpkSharp\GlpkSharp\
for the mapping of individual functions and constants.

You can find the documentation of the GLPK functions available for
GLPK# in fileglpk-4.42\doc\gmpl.pdf of the source distribution of 
GLPK available at
ftp://ftp.gnu.org/gnu/glpk/glpk-4.42.tar.gz

---

Concerning your 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
What do these numbers imply? Could technician 2 do the job for
customer 1 in 9.30 hours, while technician 3 would need 5.3 hours
for the same job to be done?

Concerning your code:
Arrays in C start at index 0. GLPK only uses the values for
indices 1 and above.

The default column type is FLOAT. You centainly want to set the
column type to BINARY.

Best regards

Xypron

-------- Original-Nachricht --------
> Datum: Thu, 14 Oct 2010 12:26:07 +0700
> Betreff: [Help-glpk] One more question about how to use GLPK for specific     
> problem

> 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
> 
> _______________________________________________
> Help-glpk mailing list
> address@hidden
> http://lists.gnu.org/mailman/listinfo/help-glpk

-- 
Neu: GMX De-Mail - Einfach wie E-Mail, sicher wie ein Brief!  
Jetzt De-Mail-Adresse reservieren: http://portal.gmx.net/de/go/demail