Re: [eclipse-clp-users] Q: Linear Programming with Disjunction constraints

Hi Kim,

Kim Lai wrote:
>
>
> ---------- Forwarded message ----------
> From: *Kim Lai* <kim73327_at_gmail.com <mailto:kim73327_at_gmail.com>>
> Date: Apr 23, 2008 10:56 PM
> Subject: Q: Linear Programming with Disjunction constraints
> To: eclipse-clp-users_at_lists.sf.net <mailto:eclipse-clp-users_at_lists.sf.net>
>
> hi, I'm new to eclipse. Here looks for a great HELP.
> after studying the documents... I still have trouble with my problem.
> I don't know how to use lib(eplex) for 
> 1. disjunctive constraints
> 2. get a maximum among lots Varables
>
The ECLiPSe documentation on eplex is not really designed to teach you 
linear programming, or even constraint programming You would need to 
read other source material (e.g. textbooks on linear programming and 
constraint programming) for this.

However, the issue of disjunctive constraint (which are non-linear, and 
therefore cannot be directly modelled in linear programming) is 
discussed in the ECLiPSe tutorial, in the chapter `Building Hybrid 
Algorithms' (section 'Handling Disjunctions').

A well known aproach in linear programming to model disjunctions is to 
use `Big-M constraints' -- this is discussed in the tutorial chapter.

For your point 2, see below.

> I'd like to formulate a problem like this:
> ------------------------------------------------------------------------------
> Vars = [ t1, t2, t3 ]
> Vars :: 0.0..inf
>
> % constraints
> (t1 - t2 <= -10.2  or  t1 - t2 >= 15.6) and
> (t2 - t3 <= -3.1 or t2 - t3 >= 9.8 )
> % goal ( cost )
> try to minimize( Maximum among( t1 + 14.5, t2+1.4, t3+ 4.5 ) )
> -------------------------------------------------------------------------

Looking at your example, you seem to be trying to model some sort of job 
scheduling problem. The standard technique to model the minimum time to 
complete a schedule is to add a `dummy' task that can only start after 
all the other tasks have completed, and minimise the start time of this 
task as your objective.

If you are to model this in ic, you probably want to use finite domain 
rather than real intervals -- to do this you need to have integers only, 
so you need to choose your time unit so that they are integer, for your 
example, this would seem to be in units of 0.1 seconds rather than seconds.

This sort of problem can also be modelled as a linear problem using 
Big-M constraints.

The example page of the ECLiPSe website has several scheduling examples 
(under the Planning and Scheduling section) which you might find useful 
to look at:

http://www.eclipse-clp.org/examples/index.html

I will take a look at your specific code to see why you are getting the 
error you are getting, but you should not need to use maxlist/2 with the 
dummy task approach.

Cheers,

Kish