Notes from Asg1

Comment Rubrica

1. Introduce notation before use in equations.

2. Term not defined. Define before use.

3. Distinguish Variables and Parameters.

4. An explanation is missing.

5. Prefer use of single letters in mathematical symbols.

6. Reserve x,y,z, letters to variables.

7. Avoid more than one nested indexes: $A_{s}$ fine, $A_{s_p}$ less fine.

8. More precision required, use mathematical notation.

9. Details missing: solver, time limit, computer architecture.

10. Incorrect mathematical notation.

11. Submission not compliant to the requirements.

12. Solution evaluation by the validator is different than reported.

Evaluation Criteria

1. performance: have the results been validated? how does the quality of the solutions rank with respect to the others reports? Are the time limit and the computational resources reported and equal among the reports?
2. model: the way constraints are written, are they concise and effective or hardcoded and specific? If original, is the model sensible?
3. description: is the language precise with use of proper terminology and mathematical symbols to make concepts clear or is it vague and unclear? Is the document well structured?

Results from the voting

Twelve different ranks were submitted at the Pnyx page. They can be see from the preflib page. The final ranking can be seen from the final results page.

Marco did not vote. If he did hix s ranking would have been c,{b,e…},{a,…},{d,…}…

Marco’s solutions

Solvers make a big difference and or-tools is currently the golden medal in several categories at the yearly MiniZinc Challenge.

My results (sorry for the incompleteness but the most indicative are there):

The table is generated running:

% gecode
$ minizinc Solver/model.mzn Instances/example.dzn --time-limit 600000 -s -i --solver-statistics -O5
% chuffed
$ minizinc Solver/model.mzn Instances/example.dzn --time-limit 600000 -s -i -f --solver org.chuffed.chuffed
% or-tools
$ minizinc Solver/model.mzn Instances/example.dzn --time-limit 600000 -s -i -f --solver org.ortools.ortools

Unfortunately, except for or-tools for the other solvers it seems not possible to retrieve the time at which the best solution is found so the time reported is the time limit but the soluton was found much earlier.

To install or-tools:

• download the executable for your architecture from https://developers.google.com/optimization/install

• or build from source using the instructions for cmake linked in the github page.

• configure following the instructions from 3.2.5.2 Adding Third-Party Solvers of the MiniZinc Handbook (page 172). You can also write the configuration file directly and put it in one of the locations described in 4.3.5. Solver Configuration Files. The configuration file from 3.12.2.4. OR Tools seems outdated. In particular, after the compilation I could not find a solver-specific MiniZinc library, so I left that field empty, the MiniZinc standard library will be used.

or-tools supports many of MiniZinc’s global constraints natively. It often performs better multi-threaded (option -p) so it can employ various solving technologies. A search annotation can be useful, however allowing OR-Tools to mix the prescribed strategy with its own (option -f free search, ignore search annotations) usually is best.

minizinc MiniZincModel/Talent.mzn Instances/example.dzn –solver org.minizinc.globalizer

Globalizer

The solver Globalizer (3.7 Globalizer) can be used to discover global constraints from the models.

minizinc MiniZincModel/Talent.mzn --solver org.minizinc.globalizer

Unfortunately for the model below it did not yield any recommendation (while there should be at least one for the value_precede constraint).

Marco’s MiniZinc model

include "alldifferent.mzn";
include "value_precede_chain.mzn";

int: NumActors;
int: NumScenes;
int: NumLocations;
int: NumPrecedences;

% arrays in MiniZinc are 1 indexed because enums are
array[1..NumActors] of int: ActorCost;
array[1..NumLocations] of int: LocationCost;
array[1..NumScenes] of int: SceneDuration;
array[1..NumScenes] of int: SceneLocation;
array[1..NumActors,1..NumScenes] of 0..1: Presence;
array[1..NumPrecedences, 1..2] of int: Precedences;

int: UBLocationFootprint=max(LocationCost) * NumScenes; 
int: UBActorFootprint=sum(a in 1..NumActors, s in 1..NumScenes)(ActorCost[a]*SceneDuration[s]); 

% Variables
array[1..NumScenes] of var 1..NumScenes: Order;
var 0..UBLocationFootprint: LocationFootprint;
var 0..UBActorFootprint: ActorFootprint;
var 0..UBLocationFootprint+UBActorFootprint: TotalFootprint;

constraint alldifferent(Order);

constraint TotalFootprint = ActorFootprint + LocationFootprint;

%scene precedence
constraint forall(r in (1..NumPrecedences))
  (value_precede_chain([x+1 | x in row(Precedences,r)], Order));

% Location footprint
constraint LocationFootprint = sum(i in 1..NumScenes)
  (if i >= 2 /\ SceneLocation[Order[i]] == SceneLocation[Order[i-1]] then 0 
   else LocationCost[SceneLocation[Order[i]]+1]  endif)
    - sum(l in LocationCost)(l);


% Actor footprint
array[1..NumActors] of var int: start :: no_output;
array[1..NumActors] of var int: end :: no_output;
%array[1..NumActors] of int: p = row(Presence, a);

constraint forall(a in 1..NumActors)(
    start[a] = min(i in 1..NumScenes where Presence[Order[i],a] == 1)(i) /\
    end[a] = max(i in 1..NumScenes where Presence[Order[i],a] == 1)(i)
);
     
constraint ActorFootprint = sum(a in 1..NumActors)
  (
    sum(i in 1..NumScenes)
    ( if start[a]<=i /\ i<=end[a] then ActorCost[a] * SceneDuration[Order[i]] else 0 endif)
  ) - sum(a in 1..NumActors, s in 1..NumScenes)(ActorCost[a]*SceneDuration[s]*Presence[a,s]);

 
% Optim
constraint LocationFootprint <= max(LocationCost) * NumScenes; 
constraint LocationFootprint <= TotalFootprint;
constraint ActorFootprint <= TotalFootprint;


solve :: seq_search([/*[int_search([ActorFootprint], dom_w_deg, indomain_max),*/
  int_search(Order, dom_w_deg, indomain_median)]) minimize TotalFootprint;