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

From: Kish Shen <kisshen_at_cisco.com>
Date: Thu, 05 Aug 2010 01:16:17 +0100
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.

> So, maybe I am misunderstanding what is passed to the MILP solver;
> I try to save the model in an mps file:
> 
> go:-
>      eplex_solver_setup(min(Y)),
>      X :: 0..10,
>      Y :: 0..10,
>      piecewise_linear_hull(X, [(0,0), (1,2), (3,3)], Y),
>      eplex_write(mps,'piece.mps').
> 
> and I get the file:
> 
> ------------------------------------------------
> NAME          eclipse
> ROWS
>   N  obj
> COLUMNS
>      x1        obj                             1
>      x2        obj                             0
> RHS
> BOUNDS
>   UP bnd       x1                             10
>   UP bnd       x2                             10
> ENDATA
> ------------------------------------------------
> 
> but there is no SOS section.
> 
> But, maybe I can create an MPS file without SOS, add myself an SOS 
> section, and then explicitly load the MPS from the MILP solver.

 From what you are saying here, it seems that you expect your call to 
piecewise_lnear_hull/3 will add SOS to a problem. As I said, I don't 
believe it does this.

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.

If you want to add SOS explicitly to your problem, you can do so via 
eplex_solver_setup/4, rather than trying to modify the MPS file.

> Of course, in a large project I cannot find which variables should be in 
> an SOS if they are named x1, x2, ...
> Looking at the manual page for eplex_set/2, I find the use_var_names option.
> 
> So I try
> 
> :- lib(var_name).
> go2(X,Y):-
>      eplex_solver_setup(min(Y)),
>      eplex_set(use_var_names,yes),
>      X :: 0..10, set_var_name(X,"X"),
>      Y :: 0..10, set_var_name(Y,"Y"),
>      eplex_write(mps,'piece.mps').
> 
> I get the warning
> 
> [eclipse 10]: go2(X,Y).
> Default column names x1, x2 ... being created.
> 
> X = X#0{0.0 .. 10.0}
> Y = Y#0{0.0 .. 10.0}
> Yes (0.00s cpu)
> 
> and, in fact, the piece.mps file has not changed.
> 
> What am I doing wrong?
> 

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.

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!)

Cheers,

Kish

-- 
This e-mail may contain confidential and privileged material for the
sole use of the intended recipient. Any review, use, distribution or
disclosure by others is strictly prohibited. If you are not the intended
recipient (or authorized to receive for the recipient), please contact
the sender by reply e-mail and delete all copies of this message.
Cisco Systems Limited (Company Number: 02558939), is registered in
England and Wales with its registered office at 1 Callaghan Square,
Cardiff, South Glamorgan CF10 5BT.
Received on Thu Aug 05 2010 - 00:16:25 CEST

This archive was generated by hypermail 2.2.0 : Thu Feb 02 2012 - 02:31:58 CET