Re: [eclipse-clp-users] Piecewise Linear functions

Hi Kish,

On 05/08/10 02:16, Kish Shen wrote:
> Hi Marco,
>
> Marco Gavanelli wrote:
>> Dear all,
>>
>> I am trying to use Eplex with a piecewise linear function.
>> My intention was to use Special Order Sets (SOS), but I am probably
>> misunderstanding how I can use them.
>>
>> My first attempt was to use piecewise_linear_hull/3:
>>
>> go(X,Y,V):-
>> X :: 0..10,
>> Y :: 0..10,
>> piecewise_linear_hull(X, [(0,2), (1,2), (3,1), (10,10)], Y),
>> optimize(min(Y), V).
>>
>> [eclipse 2]: go(X,Y,V).
>> Eplex warning: Imposing integer bounds on variable(s) X for eplex
>> instance eplex does not impose integer type.
>> Eplex warning: Imposing integer bounds on variable(s) Y for eplex
>> instance eplex does not impose integer type.
>> WARNING: module 'eplex_relax' does not exist, loading library...
>> No (0.08s cpu)
>>
>
> I am not very familiar with piecewise_linear_hull/3, except that it is
> intended for in conjunction with lib(ic), with a relaxed version of the
> piecewise linear function added to the eplex problem instance.
>
> I am not sure what you mean by using SOS: as far as I can tell,
> piecewise_linear_hull does not use SOS, and the code you show also does
> not use SOS. You can pass SOS information (SOS1 and SOS2) to the
> external solver when you set up the problem, if you use
> eplex_solver_setup/4 -- sos1 and sos2 can be passed to the external
> solvers in the options argument.

Yes, indeed, I had excluded this option because the manual of 
eplex_solver_setup/4 says

  "ListOfOptions are (such option should occur no more than once)"

and I need to have more than one SOS. Now I tried creating a list of 
options that contains more than one term sos2(...) and it works, thank 
you for the explanation! Maybe you could say in the manual that actually 
there can be more than one sos() or sos2() terms in the ListOfOptions.

> Secondly, I am not certain that MPS supports SOS -- I am not very
> familiar with MPS, but the basic (i.e. standard) MPS cannot even specify
> the optimisation direction (it assumes you are minimsing), so I would be
> surprised if SOS is supported. It is possible that the solver you are
> using (and I guess you are using CPLEX from the message about default
> names) does support SOS in its extended (and therefore non-standard) MPS
> format.

Yes, CPLEX supports it, and, in fact, eplex_write creates the SOS 
section if sos2(...) was specified in the ListOfOptions.
I had found this page:

http://lpsolve.sourceforge.net/5.1/mps-format.htm

mentioning SOS in MPS, and I guess it is on lpsolve, so I guess nowadays 
SOS are considered in most solvers.

> For var_names to be passed to the external solver, the variable must
> already have a var_name when you pass it to the solver. In your example,
> you pass the variable to the solver with ::/2, e.g. X :: 0..10, but you
> only add the var_name after this, with set_var_name, so you should swap
> the order of the two goals if you want the name to appear in your MPS file.

Ok, thank you for the information.

> On a more general point about piecewise linear functions, in reading the
> external solvers' manuals when I was trying to implement some of the
> functionality of eplex, I remember seeing mention of piecewise linear
> functions, although I cannot remember in what context, or indeed which
> solver(s), but it does seem some solvers may support piecewise linear
> functions. If this is the case, then it is also possible for eplex to
> support it, so if there is sufficient interest, I can look more closely
> into this, but any such enhancement to eplex will not happen in the
> short-term, i.e. only after ECLiPSe 6.1 is released. Given, do let me
> know if you think it is worthwhile (of course, as ECLiPSe is
> open-source, you can also add the functionality yourself, and we will
> welcome any such contributions!)

Well, I cannot say I will use it every day, but I think it can be useful.
It mainly depends on whether the external solver does something more 
clever or it just imposes an SOS.
In the second case, I think that an explanation in the manual on how to 
implement a piecewise linear function through an SOS could be enough.

Thank you very much for your quick answer!
Marco

-- 
Marco Gavanelli, Ph.D. in Computer Science
Dept of Engineering
University of Ferrara
Tel/Fax  +39-0532-97-4833
http://www.ing.unife.it/docenti/MarcoGavanelli/