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

From: Kish Shen <kisshen_at_...5...>
Date: Wed, 23 Apr 2008 17:52:29 +0100
```Hi Kim,

Kim Lai wrote:
>
>
> ---------- Forwarded message ----------
> From: *Kim Lai* <kim73327_at_...6... <mailto:kim73327@...6...>>
> Date: Apr 23, 2008 10:56 PM
> Subject: Q: Linear Programming with Disjunction constraints
> To: eclipse-clp-users_at_...105... <mailto:eclipse-clp-users@...105...>
>
> 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

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