Car Sequencing Problem with Colors
Problem
The Car Sequencing Problem with Paint-Shop Batching Constraints involves scheduling the production of a set of cars. The cars are not identical, and different options are available as variants of the basic model. The assembly line has different stations to install the various options (air conditioning, sunroof, etc.). These stations have a maximum capacity. They can handle up to a certain percentage of cars passing along the assembly line. Therefore, the cars must be arranged in a sequence so that the capacity of each station is never exceeded. Furthermore, spray guns must be washed with paint solvent regularly and in between two different car colors.
This Problem was initially submitted by the car manufacturer Renault for the 2005 Challenge of the French Society of Operations Research and Decision Support (ROADEF).
Principles learned
- Use a list decision variable to represent the sequence of cars
- Optimize several objectives in lexicographic order
- Differentiate structural constraints from first-priority objectives
- Use non-linear operators to compute the number of violations
Data
The format of the data files is as follows:
- 1st line: number of cars, number of options, number of classes, maximum paint batch size, objective order, start position.
- For each option: the maximum number of cars with that option in a block, the size of the block, whether or not this option is of high priority.
- For each class: color, number of cars in this class, for each option, whether or not this class requires it (1 or 0).
- For each position before the start position: the class initially planned to be produced
For more details, see the challenge website.
Program
The Hexaly model for the Car Sequencing Problem with Paint-Shop Batching Constraints uses a list decision variable representing the sequence of cars. The i-th element of the list corresponds to the index of the i-th car to build. Using the ‘partition‘ operator, we ensure that each car to be produced is present in the assembly line.
From the sequence, we can compute, for each option and each position in the line, the number of cars with this option in the window starting at this position. We can then deduce the number of violations for each option and each window. Similarly, we then use the ‘neq’ and ‘or’ operators to enforce the color change constraints.
Even though this problem is a pure satisfaction problem, we choose to add objectives to minimize the sum of capacity violations for all options and all windows. Having no capacity violation is indeed more of a “business” constraint than a structural one. If there are a few violations, the assembly chain will slow down, but it will be able to continue. On the contrary, having two cars in one spot is not physically possible in the assembly line: it is a structural constraint. See this section of the documentation for more information about the difference between high-priority objectives and hard constraints.
We define three objectives:
- Minimizing the window capacity violations for high-priority options
- Minimizing the window capacity violations for low-priority options
- Minimizing the number of color changes
The three objectives are optimized lexicographically: the order in which they are declared defines their order of importance.
- Execution
-
hexaly car_sequencing_color.hxm inFileName=instances/022_3_4_EP_RAF_ENP.in [hxTimeLimit=] [solFileName=]
use io;
/* Read instance data */
function input() {
COLOR_HIGH_LOW = 0;
HIGH_LOW_COLOR = 1;
HIGH_COLOR_LOW = 2;
COLOR_HIGH = 3;
HIGH_COLOR = 4;
local usage = "Usage: hexaly car_sequencing_color.hxm "
+ "inFileName=inputFile [solFileName=outputFile] [hxTimeLimit=timeLimit]";
if (inFileName == nil) throw usage;
local inFile = io.openRead(inFileName);
nbPositions = inFile.readInt();
nbOptions = inFile.readInt();
nbClasses = inFile.readInt();
paintBatchLimit = inFile.readInt();
objectiveOrder = inFile.readInt();
startPosition = inFile.readInt();
hasLowPriorityOptions = false;
for [o in 0...nbOptions] {
maxCarsPerWindow[o] = inFile.readInt();
windowSize[o] = inFile.readInt();
isPriorityOption[o] = (inFile.readInt() == 1);
if (!isPriorityOption[o]) hasLowPriorityOptions = true;
}
if (!hasLowPriorityOptions) {
if (objectiveOrder == COLOR_HIGH_LOW) objectiveOrder = COLOR_HIGH;
else if (objectiveOrder == HIGH_COLOR_LOW) objectiveOrder = HIGH_COLOR;
else if (objectiveOrder == HIGH_LOW_COLOR) objectiveOrder = HIGH_COLOR;
}
for [c in 0...nbClasses] {
colorClass[c] = inFile.readInt();
nbCars[c] = inFile.readInt();
options[c][o in 0...nbOptions] = (inFile.readInt()==1);
}
initialSequence[p in 0...nbPositions] = inFile.readInt();
}
/* Declare the optimization model */
function model() {
// sequence[i] = j if class initially planned on position j is produced on position i
sequence <- list(nbPositions);
// sequence is a permutation of the initial production plan, all indexes must
// appear exactly once
constraint partition(sequence);
// Past classes (before startPosition) can not move
for [p in 0...startPosition]
constraint sequence[p] == p;
// Number of cars with option o in each window
nbCarsWindows[o in 0...nbOptions][j in startPosition-windowSize[o]+1...nbPositions]
<- sum[k in 0...windowSize[o] : j + k >= 0 && j + k < nbPositions]
(options[initialSequence[sequence[j + k]]][o]);
// Number of violations of option o capacity in each window
nbViolationsWindows[o in 0...nbOptions]
<- sum[j in startPosition-windowSize[o]+1...nbPositions]
(max(0, nbCarsWindows[o][j] - maxCarsPerWindow[o]));
objectiveHighPriority <- sum[o in 0...nbOptions : isPriorityOption[o]](nbViolationsWindows[o]);
objectiveLowPriority <- sum[o in 0...nbOptions : !isPriorityOption[o]](nbViolationsWindows[o]);
// Color change between position p and position p + 1
colorChange[p in startPosition-1...nbPositions-1]
<- colorClass[initialSequence[sequence[p]]] != colorClass[initialSequence[sequence[p + 1]]];
objectiveColor <- sum[p in startPosition-1...nbPositions-1](colorChange[p]);
// Paint limit constraints: at least one change every paintBatchLimit positions
for [p in startPosition...nbPositions-paintBatchLimit-1]
constraint or[p2 in 0...paintBatchLimit](colorChange[p + p2]);
// Declare the objectives in the correct order
if(objectiveOrder == COLOR_HIGH_LOW) {
obj[0] <- objectiveColor;
obj[1] <- objectiveHighPriority;
obj[2] <- objectiveLowPriority;
} else if(objectiveOrder == HIGH_COLOR_LOW) {
obj[0] <- objectiveHighPriority;
obj[1] <- objectiveColor;
obj[2] <- objectiveLowPriority;
} else if(objectiveOrder == HIGH_LOW_COLOR) {
obj[0] <- objectiveHighPriority;
obj[1] <- objectiveLowPriority;
obj[2] <- objectiveColor;
} else if(objectiveOrder == COLOR_HIGH) {
obj[0] <- objectiveColor;
obj[1] <- objectiveHighPriority;
} else if(objectiveOrder == HIGH_COLOR) {
obj[0] <- objectiveHighPriority;
obj[1] <- objectiveColor;
}
for [o in obj] minimize o;
}
/* Parametrize the solver */
function param() {
// Set the initial solution
sequence.value.clear();
for [p in 0...nbPositions]
sequence.value.add(p);
if (hxTimeLimit == nil) hxTimeLimit = 60;
}
/* Write the solution in a file with the following format:
* - 1st line: value of the objectives;
* - 2nd line: for each position p, index of class at positions p. */
function output() {
if (solFileName == nil) return;
local solFile = io.openWrite(solFileName);
solFile.print(objectiveColor.value, " ");
solFile.print(objectiveHighPriority.value, " ");
solFile.println(objectiveLowPriority.value);
local listSolution = sequence.value;
for [p in 0...nbPositions]
solFile.print(initialSequence[listSolution[p]], " ");
solFile.println();
}
- Execution (Windows)
-
set PYTHONPATH=%HX_HOME%\bin\pythonpython car_sequencing_color.py instances\022_3_4_EP_RAF_ENP.in
- Execution (Linux)
-
export PYTHONPATH=/opt/hexaly_13_0/bin/pythonpython car_sequencing_color.py instances\022_3_4_EP_RAF_ENP.in
import hexaly.optimizer
import sys
COLOR_HIGH_LOW = 0
HIGH_LOW_COLOR = 1
HIGH_COLOR_LOW = 2
COLOR_HIGH = 3
HIGH_COLOR = 4
def read_integers(filename):
with open(filename) as f:
return [int(elem) for elem in f.read().split()]
#
# Read instance data
#
def read_instance(instance_file):
file_it = iter(read_integers(instance_file))
nb_positions = next(file_it)
nb_options = next(file_it)
nb_classes = next(file_it)
paint_batch_limit = next(file_it)
objective_order = next(file_it)
start_position = next(file_it)
max_cars_per_window = []
window_size = []
is_priority_option = []
has_low_priority_options = False
for o in range(nb_options):
max_cars_per_window.append(next(file_it))
window_size.append(next(file_it))
is_prio = next(file_it) == 1
is_priority_option.append(is_prio)
if not is_prio:
has_low_priority_options = True
if not has_low_priority_options:
if objective_order == COLOR_HIGH_LOW:
objective_order = COLOR_HIGH
elif objective_order == HIGH_COLOR_LOW:
objective_order = HIGH_COLOR
elif objective_order == HIGH_LOW_COLOR:
objective_order = HIGH_COLOR
color_class = []
nb_cars = []
options_data = []
for c in range(nb_classes):
color_class.append(next(file_it))
nb_cars.append(next(file_it))
options_data.append([next(file_it) == 1 for i in range(nb_options)])
initial_sequence = [next(file_it) for p in range(nb_positions)]
return nb_positions, nb_options, paint_batch_limit, objective_order, start_position, \
max_cars_per_window, window_size, is_priority_option, has_low_priority_options, \
color_class, options_data, initial_sequence
def main(instance_file, output_file, time_limit):
nb_positions, nb_options, paint_batch_limit, objective_order, start_position, \
max_cars_per_window, window_size, is_priority_option, has_low_priority_options, \
color_class, options_data, initial_sequence = read_instance(instance_file)
with hexaly.optimizer.HexalyOptimizer() as optimizer:
#
# Declare the optimization model
#
model = optimizer.model
# sequence[i] = j if class initially planned on position j is produced on position i
sequence = model.list(nb_positions)
# sequence is a permutation of the initial production plan, all indexes must appear
# exactly once
model.constraint(model.partition(sequence))
# Past classes (before startPosition) can not move
[model.constraint(sequence[p] == p) for p in range(start_position)]
# Create Hexaly arrays to be able to access them with "at" operators
initials = model.array(initial_sequence)
colors = model.array(color_class)
options = model.array(options_data)
# Number of cars with option o in each window
nb_cars_windows = [None] * nb_options
for o in range(nb_options):
nb_cars_windows[o] = [None] * nb_positions
for j in range(start_position - window_size[o] + 1, nb_positions):
nb_cars_windows[o][j] = model.sum()
for k in range(window_size[o]):
if j + k >= 0 and j + k < nb_positions:
class_at_position = initials[sequence[j + k]]
nb_cars_windows[o][j].add_operand(model.at(
options,
class_at_position,
o))
# Number of violations of option o capacity in each window
objective_high_priority = model.sum()
if has_low_priority_options:
objective_low_priority = model.sum()
for o in range(nb_options):
nb_violations_windows = model.sum(
model.max(
nb_cars_windows[o][p] - max_cars_per_window[o], 0)
for p in range(start_position - window_size[o] + 1, nb_positions))
if is_priority_option[o]:
objective_high_priority.add_operand(nb_violations_windows)
else:
objective_low_priority.add_operand(nb_violations_windows)
# Color change between position p and position p + 1
color_change = [None] * (nb_positions - 1)
objective_color = model.sum()
for p in range(start_position - 1, nb_positions - 1):
current_class = initials[sequence[p]]
next_class = initials[sequence[p + 1]]
color_change[p] = colors[current_class] != colors[next_class]
objective_color.add_operand(color_change[p])
# Paint limit constraints: at least one change every paintBatchLimit positions
for p in range(start_position, nb_positions - paint_batch_limit - 1):
node_or = model.or_(color_change[p + p2] for p2 in range(paint_batch_limit))
model.constraint(node_or)
# Declare the objectives in the correct order
if objective_order == COLOR_HIGH_LOW:
model.minimize(objective_color)
model.minimize(objective_high_priority)
model.minimize(objective_low_priority)
elif objective_order == HIGH_COLOR_LOW:
model.minimize(objective_high_priority)
model.minimize(objective_color)
model.minimize(objective_low_priority)
elif objective_order == HIGH_LOW_COLOR:
model.minimize(objective_high_priority)
model.minimize(objective_low_priority)
model.minimize(objective_color)
elif objective_order == COLOR_HIGH:
model.minimize(objective_color)
model.minimize(objective_high_priority)
elif objective_order == HIGH_COLOR:
model.minimize(objective_high_priority)
model.minimize(objective_color)
model.close()
# Set the initial solution
sequence.get_value().clear()
for p in range(nb_positions):
sequence.get_value().add(p)
# Parameterize the optimizer
optimizer.param.time_limit = time_limit
optimizer.solve()
#
# Write the solution in a file with the following format:
# - 1st line: value of the objectives;
# - 2nd line: for each position p, index of class at positions p.
#
if output_file is not None:
with open(output_file, 'w') as f:
f.write("%d " % objective_color.value)
f.write("%d " % objective_high_priority.value)
f.write("%d\n" % objective_low_priority.value)
for p in range(nb_positions):
f.write("%d " % sequence.value[p])
f.write("\n")
if __name__ == '__main__':
if len(sys.argv) < 2:
print("Usage: python car_sequencing_color.py instance_file [output_file] [time_limit]")
sys.exit(1)
instance_file = sys.argv[1]
output_file = sys.argv[2] if len(sys.argv) >= 3 else None
time_limit = int(sys.argv[3]) if len(sys.argv) >= 4 else 60
main(instance_file, output_file, time_limit)
- Compilation / Execution (Windows)
-
cl /EHsc car_sequencing_color.cpp -I%HX_HOME%\include /link %HX_HOME%\bin\hexaly130.libcar_sequencing_color instances/022_3_4_EP_RAF_ENP.in
- Compilation / Execution (Linux)
-
g++ car_sequencing_color.cpp -I/opt/hexaly_13_0/include -lhexaly130 -lpthread -o car_sequencing_color./car_sequencing_color instances/022_3_4_EP_RAF_ENP.in
#include "optimizer/hexalyoptimizer.h"
#include <fstream>
#include <iostream>
#include <vector>
using namespace hexaly;
using namespace std;
#define COLOR_HIGH_LOW (0)
#define HIGH_LOW_COLOR (1)
#define HIGH_COLOR_LOW (2)
#define COLOR_HIGH (3)
#define HIGH_COLOR (4)
class CarSequencingColor {
public:
// Number of vehicles
int nbPositions;
// Number of options
int nbOptions;
// Number of classes
int nbClasses;
// Paint batch limit
int paintBatchLimit;
// Objective order
int objectiveOrder;
// Start position
int startPosition;
// Options properties
vector<int> maxCarsPerWindow;
vector<int> windowSize;
vector<bool> isPriorityOption;
bool hasLowPriorityOptions;
// Classes properties
vector<int> colorClass;
vector<int> nbCars;
vector<vector<bool>> optionsData;
// Initial sequence
vector<int> initialSequence;
// Hexaly Optimizer
HexalyOptimizer optimizer;
// Hexaly Program variable
HxExpression sequence;
// Objectives
HxExpression objectiveColor;
HxExpression objectiveHighPriority;
HxExpression objectiveLowPriority;
/* Read instance data */
void readInstance(const string& fileName) {
ifstream infile;
infile.exceptions(ifstream::failbit | ifstream::badbit);
infile.open(fileName.c_str());
infile >> nbPositions;
infile >> nbOptions;
infile >> nbClasses;
infile >> paintBatchLimit;
infile >> objectiveOrder;
infile >> startPosition;
maxCarsPerWindow.resize(nbOptions);
windowSize.resize(nbOptions);
isPriorityOption.resize(nbOptions);
hasLowPriorityOptions = false;
for (int o = 0; o < nbOptions; ++o) {
infile >> maxCarsPerWindow[o];
infile >> windowSize[o];
int tmp;
infile >> tmp;
isPriorityOption[o] = (tmp == 1);
if (!isPriorityOption[o])
hasLowPriorityOptions = true;
}
if (!hasLowPriorityOptions) {
if (objectiveOrder == COLOR_HIGH_LOW)
objectiveOrder = COLOR_HIGH;
else if (objectiveOrder == HIGH_COLOR_LOW)
objectiveOrder = HIGH_COLOR;
else if (objectiveOrder == HIGH_LOW_COLOR)
objectiveOrder = HIGH_COLOR;
}
optionsData.resize(nbClasses);
nbCars.resize(nbClasses);
colorClass.resize(nbClasses);
for (int c = 0; c < nbClasses; ++c) {
infile >> colorClass[c];
infile >> nbCars[c];
optionsData[c].resize(nbOptions);
for (int o = 0; o < nbOptions; ++o) {
int v;
infile >> v;
optionsData[c][o] = (v == 1);
}
}
initialSequence.resize(nbPositions);
for (int p = 0; p < nbPositions; ++p)
infile >> initialSequence[p];
}
void solve(int limit) {
// Declare the optimization model
HxModel model = optimizer.getModel();
// sequence[i] = j if class initially planned on position j is produced on position i
sequence = model.listVar(nbPositions);
// sequence is a permutation of the initial production plan, all indexes must appear exactly once
model.addConstraint(model.partition(sequence));
// Past classes (before startPosition) can not move
for (int p = 0; p < startPosition; ++p)
model.addConstraint(sequence[p] == p);
// Create HexalyOptimizer arrays to be able to access them with "at" operators
HxExpression initials = model.array(initialSequence.begin(), initialSequence.end());
HxExpression colors = model.array(colorClass.begin(), colorClass.end());
HxExpression options = model.array();
for (int c = 0; c < nbClasses; ++c) {
HxExpression classOptions = model.array(optionsData[c].begin(), optionsData[c].end());
options.addOperand(classOptions);
}
// Number of cars with option o in each window
vector<vector<HxExpression>> nbCarsWindows;
nbCarsWindows.resize(nbOptions);
for (int o = 0; o < nbOptions; ++o) {
nbCarsWindows[o].resize(nbPositions);
for (int j = startPosition - windowSize[o] + 1; j < nbPositions; ++j) {
nbCarsWindows[o][j] = model.sum();
for (int k = 0; k < windowSize[o]; ++k) {
if (j + k >= 0 && j + k < nbPositions) {
HxExpression classAtPosition = initials[sequence[j + k]];
nbCarsWindows[o][j].addOperand(model.at(options, classAtPosition, o));
}
}
}
}
// Number of violations of option o capacity in each window
objectiveHighPriority = model.sum();
if (hasLowPriorityOptions)
objectiveLowPriority = model.sum();
for (int o = 0; o < nbOptions; ++o) {
HxExpression nbViolationsWindows = model.sum();
for (int j = startPosition - windowSize[o] + 1; j < nbPositions; ++j) {
nbViolationsWindows.addOperand(model.max(0, nbCarsWindows[o][j] - maxCarsPerWindow[o]));
}
if (isPriorityOption[o])
objectiveHighPriority.addOperand(nbViolationsWindows);
else
objectiveLowPriority.addOperand(nbViolationsWindows);
}
// Color change between position p and position p + 1
vector<HxExpression> colorChange;
colorChange.resize(nbPositions - 1);
objectiveColor = model.sum();
for (int p = startPosition - 1; p < nbPositions - 1; ++p) {
HxExpression currentClass = initials[sequence[p]];
HxExpression nextClass = initials[sequence[p + 1]];
colorChange[p] = colors[currentClass] != colors[nextClass];
objectiveColor.addOperand(colorChange[p]);
}
// Paint limit constraints: at least one change every paintBatchLimit positions
for (int p = startPosition; p < nbPositions - paintBatchLimit - 1; ++p) {
HxExpression nodeOr = model.or_();
for (int p2 = 0; p2 < paintBatchLimit; ++p2)
nodeOr.addOperand(colorChange[p + p2]);
model.addConstraint(nodeOr);
}
// Declare the objectives in the correct order
switch (objectiveOrder) {
case COLOR_HIGH_LOW:
model.minimize(objectiveColor);
model.minimize(objectiveHighPriority);
model.minimize(objectiveLowPriority);
break;
case HIGH_COLOR_LOW:
model.minimize(objectiveHighPriority);
model.minimize(objectiveColor);
model.minimize(objectiveLowPriority);
break;
case HIGH_LOW_COLOR:
model.minimize(objectiveHighPriority);
model.minimize(objectiveLowPriority);
model.minimize(objectiveColor);
break;
case COLOR_HIGH:
model.minimize(objectiveColor);
model.minimize(objectiveHighPriority);
break;
case HIGH_COLOR:
model.minimize(objectiveHighPriority);
model.minimize(objectiveColor);
break;
}
model.close();
// Set the initial solution
sequence.getCollectionValue().clear();
for (int p = 0; p < nbPositions; ++p)
sequence.getCollectionValue().add(p);
// Parametrize the optimizer
optimizer.getParam().setTimeLimit(limit);
optimizer.solve();
}
/* Write the solution in a file with the following format:
* - 1st line: value of the objectives;
* - 2nd line: for each position p, index of class at positions p. */
void writeSolution(const string& fileName) {
ofstream outfile;
outfile.exceptions(ofstream::failbit | ofstream::badbit);
outfile.open(fileName.c_str());
outfile << objectiveColor.getValue() << " ";
outfile << objectiveHighPriority.getValue() << " ";
outfile << objectiveLowPriority.getValue() << endl;
for (int p = 0; p < nbPositions; ++p) {
outfile << initialSequence[sequence.getCollectionValue().get(p)] << " ";
}
outfile << endl;
}
};
int main(int argc, char** argv) {
if (argc < 2) {
cerr << "Usage: car_sequencing_color inputFile [outputFile] [timeLimit]" << endl;
return 1;
}
const char* instanceFile = argv[1];
const char* outputFile = argc >= 3 ? argv[2] : NULL;
const char* strTimeLimit = argc >= 4 ? argv[3] : "60";
try {
CarSequencingColor model;
model.readInstance(instanceFile);
model.solve(atoi(strTimeLimit));
if (outputFile != NULL)
model.writeSolution(outputFile);
return 0;
} catch (const exception& e) {
cerr << "An error occurred: " << e.what() << endl;
return 1;
}
}
- Compilation / Execution (Windows)
-
copy %HX_HOME%\bin\Hexaly.NET.dll .csc CarSequencingColor.cs /reference:Hexaly.NET.dllCarSequencingColor instances\022_3_4_EP_RAF_ENP.in
using System;
using System.IO;
using Hexaly.Optimizer;
public class CarSequencingColor : IDisposable
{
const int COLOR_HIGH_LOW = 0;
const int HIGH_LOW_COLOR = 1;
const int HIGH_COLOR_LOW = 2;
const int COLOR_HIGH = 3;
const int HIGH_COLOR = 4;
// Number of vehicles
int nbPositions;
// Number of options
int nbOptions;
// Number of classes
int nbClasses;
// Paint batch limit
int paintBatchLimit;
// Objective order
int objectiveOrder;
// Start position
int startPosition;
// Options properties
int[] maxCarsPerWindow;
int[] windowSize;
bool[] isPriorityOption;
bool hasLowPriorityOptions;
// Classes properties
int[] colorClass;
int[] nbCars;
int[][] optionsData;
// Initial sequence
int[] initialSequence;
// Hexaly Optimizer
HexalyOptimizer optimizer;
// LS Program variable
HxExpression sequence;
// Objectives
HxExpression objectiveColor;
HxExpression objectiveHighPriority;
HxExpression objectiveLowPriority;
public CarSequencingColor()
{
optimizer = new HexalyOptimizer();
}
/* Read instance data */
void ReadInstance(string fileName)
{
using (StreamReader input = new StreamReader(fileName))
{
string[] splitted = input.ReadLine().Split(' ');
nbPositions = int.Parse(splitted[0]);
nbOptions = int.Parse(splitted[1]);
nbClasses = int.Parse(splitted[2]);
paintBatchLimit = int.Parse(splitted[3]);
objectiveOrder = int.Parse(splitted[4]);
startPosition = int.Parse(splitted[5]);
maxCarsPerWindow = new int[nbOptions];
windowSize = new int[nbOptions];
isPriorityOption = new bool[nbOptions];
hasLowPriorityOptions = false;
for (int o = 0; o < nbOptions; ++o)
{
splitted = input.ReadLine().Split(' ');
maxCarsPerWindow[o] = int.Parse(splitted[0]);
windowSize[o] = int.Parse(splitted[1]);
isPriorityOption[o] = int.Parse(splitted[2]) == 1;
if (!isPriorityOption[o])
hasLowPriorityOptions = true;
}
if (!hasLowPriorityOptions)
{
if (objectiveOrder == COLOR_HIGH_LOW)
objectiveOrder = COLOR_HIGH;
else if (objectiveOrder == HIGH_COLOR_LOW)
objectiveOrder = HIGH_COLOR;
else if (objectiveOrder == HIGH_LOW_COLOR)
objectiveOrder = HIGH_COLOR;
}
optionsData = new int[nbClasses][];
nbCars = new int[nbClasses];
colorClass = new int[nbClasses];
for (int c = 0; c < nbClasses; ++c)
{
splitted = input.ReadLine().Split(' ');
colorClass[c] = int.Parse(splitted[0]);
nbCars[c] = int.Parse(splitted[1]);
optionsData[c] = new int[nbOptions];
for (int o = 0; o < nbOptions; ++o)
{
int v = int.Parse(splitted[o + 2]);
optionsData[c][o] = (v == 1) ? 1 : 0;
}
}
initialSequence = new int[nbPositions];
for (int p = 0; p < nbPositions; ++p)
initialSequence[p] = int.Parse(input.ReadLine());
}
}
public void Dispose()
{
if (optimizer != null)
optimizer.Dispose();
}
void Solve(int limit)
{
optimizer = new HexalyOptimizer();
// Declare the optimization model
HxModel model = optimizer.GetModel();
// sequence[i] = j if class initially planned on position j is produced on position i
sequence = model.List(nbPositions);
// sequence is a permutation of the initial production plan, all indexes must appear exactly once
model.Constraint(model.Partition(sequence));
// Past classes (before startPosition) can not move
for (int p = 0; p < startPosition; ++p)
model.Constraint(sequence[p] == p);
// Create HexalyOptimizer arrays to be able to access them with "at" operators
HxExpression initials = model.Array(initialSequence);
HxExpression colors = model.Array(colorClass);
HxExpression options = model.Array(optionsData);
// Number of cars with option o in each window
HxExpression[][] nbCarsWindows = new HxExpression[nbOptions][];
for (int o = 0; o < nbOptions; ++o)
{
nbCarsWindows[o] = new HxExpression[nbPositions];
for (int j = startPosition - windowSize[o] + 1; j < nbPositions; ++j)
{
nbCarsWindows[o][j] = model.Sum();
for (int k = 0; k < windowSize[o]; ++k)
{
if (j + k >= 0 && j + k < nbPositions)
{
HxExpression classAtPosition = initials[sequence[j + k]];
nbCarsWindows[o][j].AddOperand(options[classAtPosition, o]);
}
}
}
}
// Number of violations of option o capacity in each window
objectiveHighPriority = model.Sum();
if (hasLowPriorityOptions)
objectiveLowPriority = model.Sum();
for (int o = 0; o < nbOptions; ++o)
{
HxExpression nbViolationsWindows = model.Sum();
for (int j = startPosition - windowSize[o] + 1; j < nbPositions; ++j)
{
nbViolationsWindows.AddOperand(
model.Max(0, nbCarsWindows[o][j] - maxCarsPerWindow[o])
);
}
if (isPriorityOption[o])
objectiveHighPriority.AddOperand(nbViolationsWindows);
else
objectiveLowPriority.AddOperand(nbViolationsWindows);
}
// Color change between position p and position p + 1
HxExpression[] colorChange = new HxExpression[nbPositions - 1];
objectiveColor = model.Sum();
for (int p = startPosition - 1; p < nbPositions - 1; ++p)
{
HxExpression currentClass = initials[sequence[p]];
HxExpression nextClass = initials[sequence[p + 1]];
colorChange[p] = colors[currentClass] != colors[nextClass];
objectiveColor.AddOperand(colorChange[p]);
}
// Paint limit constraints: at least one change every paintBatchLimit positions
for (int p = startPosition; p < nbPositions - paintBatchLimit - 1; ++p)
{
HxExpression nodeOr = model.Or();
for (int p2 = 0; p2 < paintBatchLimit; ++p2)
nodeOr.AddOperand(colorChange[p + p2]);
model.Constraint(nodeOr);
}
// Declare the objectives in the correct order
switch (objectiveOrder)
{
case COLOR_HIGH_LOW:
model.Minimize(objectiveColor);
model.Minimize(objectiveHighPriority);
model.Minimize(objectiveLowPriority);
break;
case HIGH_COLOR_LOW:
model.Minimize(objectiveHighPriority);
model.Minimize(objectiveColor);
model.Minimize(objectiveLowPriority);
break;
case HIGH_LOW_COLOR:
model.Minimize(objectiveHighPriority);
model.Minimize(objectiveLowPriority);
model.Minimize(objectiveColor);
break;
case COLOR_HIGH:
model.Minimize(objectiveColor);
model.Minimize(objectiveHighPriority);
break;
case HIGH_COLOR:
model.Minimize(objectiveHighPriority);
model.Minimize(objectiveColor);
break;
}
model.Close();
// Set the initial solution
sequence.GetCollectionValue().Clear();
for (int p = 0; p < nbPositions; ++p)
sequence.GetCollectionValue().Add(p);
// Parametrize the optimizer
optimizer.GetParam().SetTimeLimit(limit);
optimizer.Solve();
}
/* Write the solution in a file with the following format:
* - 1st line: value of the objectives;
* - 2nd line: for each position p, index of class at positions p. */
void WriteSolution(string fileName)
{
using (StreamWriter output = new StreamWriter(fileName))
{
output.Write(objectiveColor.GetValue() + " ");
output.Write(objectiveHighPriority.GetValue() + " ");
output.WriteLine(objectiveLowPriority.GetValue());
for (int p = 0; p < nbPositions; ++p)
output.Write(initialSequence[sequence.GetCollectionValue().Get(p)] + " ");
output.WriteLine();
}
}
public static void Main(string[] args)
{
if (args.Length < 1)
{
Console.WriteLine("Usage: CarSequencingColor inputFile [outputFile] [timeLimit]");
Environment.Exit(1);
}
string instanceFile = args[0];
string outputFile = args.Length > 1 ? args[1] : null;
string strTimeLimit = args.Length > 2 ? args[2] : "60";
using (CarSequencingColor model = new CarSequencingColor())
{
model.ReadInstance(instanceFile);
model.Solve(int.Parse(strTimeLimit));
if (outputFile != null)
model.WriteSolution(outputFile);
}
}
}
- Compilation / Execution (Windows)
-
javac CarSequencingColor.java -cp %HX_HOME%\bin\hexaly.jarjava -cp %HX_HOME%\bin\hexaly.jar;. CarSequencingColor instances\022_3_4_EP_RAF_ENP.in
- Compilation / Execution (Linux)
-
javac CarSequencingColor.java -cp /opt/hexaly_13_0/bin/hexaly.jarjava -cp /opt/hexaly_13_0/bin/hexaly.jar:. CarSequencingColor instances\022_3_4_EP_RAF_ENP.in
import java.util.*;
import java.io.*;
import com.hexaly.optimizer.*;
public class CarSequencingColor {
private final int COLOR_HIGH_LOW = 0;
private final int HIGH_LOW_COLOR = 1;
private final int HIGH_COLOR_LOW = 2;
private final int COLOR_HIGH = 3;
private final int HIGH_COLOR = 4;
// Number of vehicles
private int nbPositions;
// Number of options
private int nbOptions;
// Number of classes
private int nbClasses;
// Paint batch limit
int paintBatchLimit;
// Objective order
int objectiveOrder;
// Start position
int startPosition;
// Options properties
private int[] maxCarsPerWindow;
private int[] windowSize;
private boolean[] isPriorityOption;
boolean hasLowPriorityOptions;
// Classes properties
private int[] colorClass;
private int[] nbCars;
private int[][] optionsData;
// Initial sequence
private int[] initialSequence;
// Hexaly Optimizer
private final HexalyOptimizer optimizer;
// Hexaly Program variables
private HxExpression sequence;
// Objectives
private HxExpression objectiveColor;
private HxExpression objectiveHighPriority;
private HxExpression objectiveLowPriority;
private CarSequencingColor(HexalyOptimizer optimizer) {
this.optimizer = optimizer;
}
/* Read instance data */
private void readInstance(String fileName) throws IOException {
try (Scanner input = new Scanner(new File(fileName))) {
input.useLocale(Locale.ROOT);
nbPositions = input.nextInt();
nbOptions = input.nextInt();
nbClasses = input.nextInt();
paintBatchLimit = input.nextInt();
objectiveOrder = input.nextInt();
startPosition = input.nextInt();
maxCarsPerWindow = new int[nbOptions];
windowSize = new int[nbOptions];
isPriorityOption = new boolean[nbOptions];
hasLowPriorityOptions = false;
for (int o = 0; o < nbOptions; ++o) {
maxCarsPerWindow[o] = input.nextInt();
windowSize[o] = input.nextInt();
isPriorityOption[o] = input.nextInt() == 1;
if (!isPriorityOption[o])
hasLowPriorityOptions = true;
}
if (!hasLowPriorityOptions) {
if (objectiveOrder == COLOR_HIGH_LOW)
objectiveOrder = COLOR_HIGH;
else if (objectiveOrder == HIGH_COLOR_LOW)
objectiveOrder = HIGH_COLOR;
else if (objectiveOrder == HIGH_LOW_COLOR)
objectiveOrder = HIGH_COLOR;
}
optionsData = new int[nbClasses][nbOptions];
nbCars = new int[nbClasses];
colorClass = new int[nbClasses];
for (int c = 0; c < nbClasses; ++c) {
colorClass[c] = input.nextInt();
nbCars[c] = input.nextInt();
for (int o = 0; o < nbOptions; ++o) {
int v = input.nextInt();
optionsData[c][o] = (v == 1) ? 1 : 0;
}
}
initialSequence = new int[nbPositions];
for (int p = 0; p < nbPositions; ++p) {
initialSequence[p] = input.nextInt();
}
}
}
private void solve(int limit) {
// Declare the optimization model
HxModel model = optimizer.getModel();
// sequence[i] = j if class initially planned on position j is produced on position i
sequence = model.listVar(nbPositions);
// sequence is a permutation of the initial production plan, all indexes must appear exactly once
model.constraint(model.partition(sequence));
// Past classes (before startPosition) can not move
for (int p = 0; p < startPosition; ++p)
model.addConstraint(model.eq(model.at(sequence, p), p));
// Create HexalyOptimizer arrays to be able to access them with "at" operators
HxExpression initials = model.array(initialSequence);
HxExpression colors = model.array(colorClass);
HxExpression options = model.array(optionsData);
// Number of cars with option o in each window
HxExpression[][] nbCarsWindows = new HxExpression[nbOptions][];
for (int o = 0; o < nbOptions; ++o) {
HxExpression oExpr = model.createConstant(o);
nbCarsWindows[o] = new HxExpression[nbPositions];
for (int j = startPosition - windowSize[o] + 1; j < nbPositions; ++j) {
nbCarsWindows[o][j] = model.sum();
for (int k = 0; k < windowSize[o]; ++k) {
if (j + k >= 0 && j + k < nbPositions) {
HxExpression classAtPosition = model.at(initials, model.at(sequence, j + k));
nbCarsWindows[o][j].addOperand(model.at(options, classAtPosition, oExpr));
}
}
}
}
// Number of violations of option o capacity in each window
objectiveHighPriority = model.sum();
if (hasLowPriorityOptions)
objectiveLowPriority = model.sum();
for (int o = 0; o < nbOptions; ++o) {
HxExpression nbViolationsWindows = model.sum();
for (int j = startPosition - windowSize[o] + 1; j < nbPositions; ++j) {
HxExpression delta = model.sub(nbCarsWindows[o][j], maxCarsPerWindow[o]);
nbViolationsWindows.addOperand(model.max(0, delta));
}
if (isPriorityOption[o])
objectiveHighPriority.addOperand(nbViolationsWindows);
else
objectiveLowPriority.addOperand(nbViolationsWindows);
}
// Color change between position p and position p + 1
HxExpression[] colorChange = new HxExpression[nbPositions - 1];
objectiveColor = model.sum();
for (int p = startPosition - 1; p < nbPositions - 1; ++p) {
HxExpression currentClass = model.at(initials, model.at(sequence, p));
HxExpression nextClass = model.at(initials, model.at(sequence, p + 1));
colorChange[p] = model.neq(model.at(colors, currentClass), model.at(colors, nextClass));
objectiveColor.addOperand(colorChange[p]);
}
// Paint limit constraints : at least one change every paintBatchLimit positions
for (int p = startPosition; p < nbPositions - paintBatchLimit - 1; ++p) {
HxExpression nodeOr = model.or();
for (int p2 = 0; p2 < paintBatchLimit; ++p2)
nodeOr.addOperand(colorChange[p + p2]);
model.addConstraint(nodeOr);
}
// Declare the objectives in the correct order
switch (objectiveOrder) {
case COLOR_HIGH_LOW:
model.minimize(objectiveColor);
model.minimize(objectiveHighPriority);
model.minimize(objectiveLowPriority);
break;
case HIGH_COLOR_LOW:
model.minimize(objectiveHighPriority);
model.minimize(objectiveColor);
model.minimize(objectiveLowPriority);
break;
case HIGH_LOW_COLOR:
model.minimize(objectiveHighPriority);
model.minimize(objectiveLowPriority);
model.minimize(objectiveColor);
break;
case COLOR_HIGH:
model.minimize(objectiveColor);
model.minimize(objectiveHighPriority);
break;
case HIGH_COLOR:
model.minimize(objectiveHighPriority);
model.minimize(objectiveColor);
break;
}
model.close();
// Set the initial solution
sequence.getCollectionValue().clear();
for (int p = 0; p < nbPositions; ++p)
sequence.getCollectionValue().add(p);
// Parametrize the optimizer
optimizer.getParam().setTimeLimit(limit);
optimizer.solve();
}
/*
* Write the solution in a file with the following format:
* - 1st line: value of the objectives;
* - 2nd line: for each position p, index of class at positions p.
*/
private void writeSolution(String fileName) throws IOException {
try (PrintWriter output = new PrintWriter(fileName)) {
output.print(objectiveColor.getValue() + " ");
output.print(objectiveHighPriority.getValue() + " ");
output.println(objectiveLowPriority.getValue());
for (int p = 0; p < nbPositions; ++p) {
output.print(initialSequence[(int) sequence.getCollectionValue().get(p)] + " ");
}
output.println();
}
}
public static void main(String[] args) {
if (args.length < 1) {
System.err.println("Usage: java CarSequencingColor inputFile [outputFile] [timeLimit]");
System.exit(1);
}
String instanceFile = args[0];
String outputFile = args.length > 1 ? args[1] : null;
String strTimeLimit = args.length > 2 ? args[2] : "60";
try (HexalyOptimizer optimizer = new HexalyOptimizer()) {
CarSequencingColor model = new CarSequencingColor(optimizer);
model.readInstance(instanceFile);
model.solve(Integer.parseInt(strTimeLimit));
if (outputFile != null) {
model.writeSolution(outputFile);
}
} catch (Exception ex) {
System.err.println(ex);
ex.printStackTrace();
System.exit(1);
}
}
}