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

[Dmitriy Yun]

Hi Xypron,

> 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.
Yes, I use this wrapper.
I used the example from Program.cs to create c# code for my problem
(at least I tried to do it).
Do you mean that I can use this C# wrapper to load data from .CSV file.

> GLPK comes with a standalone solver GLPSOL which can import data
> from CSV files or an SQL database.
Am I right understand that this C# wrapper is a wrapper for GLPSOL
standalone solver?


>> 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?
Yes, correct.
Each customer can be served by only one technician.

With best regards,
Dmitry

On Thu, Oct 14, 2010 at 1:02 PM, glpk xypron <address@hidden> wrote:
> 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
>



-- 
With best regards,
Dmitry