Originally posted by: Voigtler

Hello,

i'm kind of new to CPLEX and LP in general. So i'll be very happy if anyone can help me with my scheduling-problem. I want to optimize a schedule for the treatment of goods at a machine. In a first step the goods have only different widths.

The higher the width-difference of consecutive goods is, the higher the costs are.

I want to model a cost function, which should be minimized. ==> the goods should be sorted by width

As solution i want the optimized order of goods as Gannt-Chart, but i can't find a way to compare the widths of the goods.

I'd be very happy if someone can give me a hint, how i can deal with this problem.
#ConstraintProgramming-General
#DecisionOptimization

Originally posted by: JorisK

Hey,

Answering your question without further details is rather complex. For example, which variables are you using in your model? Typically, for scheduling problems, either one of these three variables is chosen:
1. Time indexed. x_{gt}=0,1 : product g is being processed at time t
Usually time indexed formulations perform very well, specially if your time horizon is small or can be partitioned into large intervals, e.g. partioning an horizon of 1 hour into 5 minute segments.
2. Assignment based formulation. x_{gi}=0,1 if product g is the ith job being processed. If you are using multiple machines, you could use: x_{gij}: product g is the ith job being processed on machine j.
3. A flow based formulation: x_{gh}=0,1: product g is processed directly before h. (equivalent: x_{ghj} product g is processed directly before product h on machine j).

Lets assume you chose the 3th option, and you know the width of each product. Lets denote the width of product g width w_g. Then your objective could be: minimize \sum_{g\in G}\sum{h\in {G-g}} (w_g-w_h)*x_{gh}
Here G is your set with products.

The above objective is not 100% correct. The one thing you cannot really do is to take the absolute value of a calculation (that is a non-linear operation which is not possible is linear optimization). So if w_g is smaller than w_h, you have a problem. Nevertheless, this is easily fixed in the above objective by ordering the set G. Since (w_g-w_h) only uses constants, you simply make sure they are in the correct order when you write down the objective.
Similar objectives can be created using the other two types of variables.
#ConstraintProgramming-General
#DecisionOptimization

Originally posted by: Voigtler

Hey, thank you very much for your reply. I think the third option fits best for my model, but i hoped i could somehow use intervals as dvar. But i don't really understand how to do it. Is it possible to solve my problem with intervals, or do i have to use integers or something else?

So i'll explain further details of my problem to you. I have 1 machine , and 5 goods. The machine handles the goods in a row. So there's no overlaping between the treatment of the 5 goods. The goods have the widths 16,5,9,5,8.

this is my first attempt:

using CP;

int nbgoods = 5;
range allgoods = 1..nbgoods;
int width allgoods = 16,5,9,5,8;
int cost = 2;
/*
Good 1 width : 16
Good 2 width : 5
Good 3 width : 9
Good 4 width : 5
Good 5 width : 8
*/
dvar interval treatmentallgoods size 1;
minimize sum(g in allgoods) sum (h in allgoods: h != g) (width[g] - width[h])* cost * ???;

subject to {
noOverlap(treatment);

}
> JorisK wrote:
>
> Lets assume you chose the 3th option, and you know the width of each product. Lets denote the width of product g width w_g. Then your objective could be: minimize \sum_{g\in G}\sum{h\in {G-g}} (w_g-w_h)*x_{gh}
> Here G is your set with products.
>

I also don't undersand what you mean by x_{gh} ? Is it the decision variable ? Is it possible to use intervals ?
And how can i write {G-g}, that CPLEX understands what i mean?

Thank you very much again
#ConstraintProgramming-General
#DecisionOptimization

Originally posted by: JorisK

Hey,

Sorry, from your first message I was under the impression that you wanted to use ILOG Cplex instead of ILOG CP optimizer. Clex is used for linear optimization problems, whereas CP optimizer uses constraint programming. Usually, if you can model a problem as a Mixed Integer Problem, then that is often better/faster than a CP problem. I'm not an expert in ILOG CP, so I'm not sure how to model your problem. There is however a good manual included with ILOG Cplex, including an extensive section on scheduling problems.

Something else :

In your problem, you do not describe any constraints on the processing of goods. Judging from your description, you simply want to order the goods, such that the ordering minimizes the difference in size between consecutive items. This problem can be seen as a traveling salesman problem. Take a simple, complete, undirected graph: each item becomes a vertex, there are edges in between all items. Add a dummy vertex to the graph and add edges between the dummy vertex and all items. Each edge has a cost. An edge between the dummy vertex and an item has cost 0. An edge between two items has a cost which equals the difference in width. Next you want to find a tour, which starts and ends in the dummy vertex and which visits each vertex (item) exactly once, thereby minimizing the length of the tour. This is exactly the TSP problem. Efficient algorithms exist to solve the TSP problem. This problem is easily modeled as a Mixed Integer Problem. Also, if you just need to solve TSP problems, then I would use some special purpose solver, such as Concorde, which is currently the fastest TSP solver.
#ConstraintProgramming-General
#DecisionOptimization

Originally posted by: SystemAdmin

Hello,
Here is a small example with interval variables in CP Optimizer. I changed your cost function to abs(width[g] - width[h]) for illustrative purpose. The actual function can be any expression involving the difference of width between an item and its direct successor in the sequence.

using CP; 

int nbgoods = 5; range allgoods = 1..nbgoods; 

int width[allgoods] = [16, 5, 9, 5, 8]; 

int cost = 2;   dvar interval treatment[g in allgoods] size 1; dvar sequence seq in    all(g in allgoods) treatment[g] types all(g in allgoods) g;   dexpr 

float deltaw = sum(g in allgoods) abs(width[g]-width[typeOfNext(seq, treatment[g], g)]);   execute 
{ cp.setSearchPhases(cp.factory.searchPhase(seq)); 
}   minimize cost * deltaw; subject to 
{ noOverlap(seq); 
}

Let me explain a little bit:

• the interval variables treatment[g] represent the treatment activities for a given good g. Currently, their size (duration) is 1. If in your real problem if you need to model a specific duration and have some additional scheduling constraints on those activities (limited resources, precedence constraints, setup-times), this type of CP Optimizer model will really be helpful

• the sequence variable seq represents the sequence of treatment activities on the machine. Each activity treatment[g] is associated a type (an index) g. So treatment[1] has type 1, etc.

• there is a noOverlap constraint on this sequence. This states that if treatment[i] is before treatment[j] in the sequence, then treatment[i] must end before the start of treatment[j]

• for a given good g, the difference between the width of g (width[g]) and the width of the interval that is scheduled next to g in the sequence (width[typeOfNext(seq, treatment[g], g)) is used in the cost expression deltaw. See the documentation of expression typeOfNext. Note that when g is last interval in the sequence, we chose g as the value of this expression so that the cost of the last good is 0.

• I added a search phase that tells the engine to focus on fixing the values of the sequence variable seq rather before focusing on finding actual start and end values for the treatment intervals because in this problem, the main decision variable is the order of interval in the sequence, not the actual start/end values. Of course, if the scheduling problem becomes more complex and dominated by scheduling constraints (resources, precedence constraints, ...), this search phase may not be useful.

Philippe
#ConstraintProgramming-General
#DecisionOptimization

Originally posted by: Voigtler

Thank you very much.

I've now added weight and thickness of the goods to the model. If i solve the model with 5 goods, solving is done within a few ms.
But if i want to optimize the model with 7 or more goods in the Array, solving takes longer than 1 hour. In the end i want to solve a problem with about 100 goods.

What can i do to solve the problem faster?
Are there any other searchphases i can use ?
I've tried to change the tolerances, but solving took also much too long!
#ConstraintProgramming-General
#DecisionOptimization

Originally posted by: SystemAdmin

Hello,
CP Optimizer indeed focuses on computing good solutions rather than computing tight lower bounds or proving optimality. It explains why, even if your model seems not very large, the engine can't prove optimality. You can use a time-limit (or a branch or a fail limit if you want to stop deterministically) to stop the search and access the best solution found so far.

Philippe
#ConstraintProgramming-General
#DecisionOptimization

Originally posted by: Voigtler

Thanks!

I accidentially changed the time-limit for mathematical programming and not for constraint programming, so this didn't work. But now i've found the right option, so i get a good solution within very short time.

But i've got some other questions:

Is it possible to solve my problem by MP ? Or should i try it with CP ?
The documentation says CP is based on Graph theory and algorithmic. Which algorithms are used and where can i get some further information about them ?
#ConstraintProgramming-General
#DecisionOptimization

Originally posted by: Voigtler

Thanks, it worked. I accidentially changed the limits for MP and not for CP, but now i found the right options.

By the way, is it possible to solve my model by MP or do i have to use CP ?

The documentation says, CP is based on graph theory and algorithmic. Can you tell me which algorithms are used and where i can find further information about them ?
#ConstraintProgramming-General
#DecisionOptimization

Originally posted by: SystemAdmin

If the model just consists of what you describe above, that is, finding a sequence for the treatment of goods on a single machine subject to a cost that can be expressed as a sum of transition cost that only depend on pairs of consecutive goods, then as stated by JorisK, it boils down to a TSP problem and you can solve it using MP.

I think CP will become interesting if, beside these constraints and objective function on good sequencing you also need to handle other types of scheduling constraints like activity durations, precedence constraints between activities, multiple machines and machine types with limited availability, cumulative resources etc.

If you want to have an idea of the algorithms that are used to solve CP scheduling models in IBM ILOG CPLEX Optimization Studio (using CP Optimizer engine), you can have a look at this paper:

P. Laborie & D. Godard. Self-Adapting Large Neighborhood Search: Application to Single-Mode Scheduling Problems. In Proceedings of the 3rd Multidisciplinary International Conference on Scheduling: Theory and Applications (MISTA), 2007, 276-284.

If you want more general information about CP techniques, a good starting point can be the Handbook of Constraint Programming.

Philippe
#ConstraintProgramming-General
#DecisionOptimization

Originally posted by: Voigtler

// Cities 

int     n       = ...; range   Cities  = 1..n;   
// Edges -- sparse set tuple       edge        
{

int i; 

int j;
} setof(edge) Edges       = 
{<i,j> | ordered i,j in Cities
}; 

int         dist[Edges] = ...;

I've decided to try to describe my problem as TSP. So i had a look in the documentation and found the TSP example.

In my problem i want to calculate my values for the dist[] array before i write them in there.

How is it possible to set dist<1,3> = 5 for example ?
I want to program a for-loop which inserts values in the array. Can you tell me how to do it ?

If i try

dist[<1,3>] = 4

i get an error.
#ConstraintProgramming-General
#DecisionOptimization

Originally posted by: SystemAdmin

Seems in your code you are reading dist from dat file

dist[Edges] = ...;

Instead, just define it as

dist[Edges];

and then set the value as you did. This should work
#ConstraintProgramming-General
#DecisionOptimization

Originally posted by: Voigtler

It doesn't work that way.

I always get an syntax errror !
#ConstraintProgramming-General
#DecisionOptimization

Originally posted by: SystemAdmin

Can you try this one:

execute
{ 

for(e in Edges) 

if(e.i==3 && e.j==4) dist[e] = 4; 
}

#ConstraintProgramming-General
#DecisionOptimization

Originally posted by: Voigtler

using CP; 

int nbgoods = 5; range allgoods = 1..nbgoods; 

int width[allgoods] = [16, 5, 9, 5, 8]; *

int cost_narrow_broad = 2;* *

int cost_broad_narrow = 1;*   dvar interval treatment[g in allgoods] size 1; dvar sequence seq in    all(g in allgoods) treatment[g] types all(g in allgoods) g; dexpr 

float deltaw = sum(g in allgoods) abs(width[g]-width[typeOfNext(seq, treatment[g], g)]); execute 
{ cp.setSearchPhases(cp.factory.searchPhase(seq)); 
} minimize cost * deltaw; subject to 
{ noOverlap(seq); 
}

I modelled a solution as TSP, which works quite good for small problems. But for lager problems the problem is solved to slow. So i want to try it with CP to stop solving after a certain period of time, to get a good, but not optimal solution.

So i want to use the first attempt again. The problem is, that i have to distinguish between a width change from broad-->narrow and narrow-->broad.

But i have no idea, how to model it.

I hope somebody can give me a hint, how to do it
#ConstraintProgramming-General
#DecisionOptimization

Originally posted by: ol

Hello,
many ways are possible, for example, you can modify the objective function as follows:

using CP; 

int nbgoods = 5; range allgoods = 1..nbgoods; 

int width[allgoods] = [16, 5, 9, 5, 8]; 

int cost_narrow_broad = 2; 

int cost_broad_narrow = 1; dvar interval treatment[g in allgoods] size 1; dvar sequence seq in    all(g in allgoods) treatment[g] types all(g in allgoods) g; dexpr 

float cost = sum(g in allgoods) ( ((width[g]>width[typeOfNext(seq, treatment[g], g)]) * cost_broad_narrow + (width[g]<=width[typeOfNext(seq, treatment[g], g)]) * cost_narrow_broad) * abs(width[g]-width[typeOfNext(seq, treatment[g], g)])); execute 
{ cp.setSearchPhases(cp.factory.searchPhase(seq)); 
} minimize cost; subject to 
{ noOverlap(seq); 
}

Or you can take the max an not the sum of the cost terms, or you can build an array where indices are all the possible differences of widths, ... Depending on your data, some approaches may be better than others.

Regards,
Olivier
#ConstraintProgramming-General
#DecisionOptimization