Dear all,
I am stuck in the formulation of an MILP problem, where I need to min |xi - x| (or minimise the absolute difference between each element in an array), where x = A*b.
There are two obstacles I have,
1. How to represent the objective in MILP/MIP friendly formation
2. How to linearize the absolute values
Ultimately, what i want to achieve is to make elements in x (A*b) as close to each other as possible. So the other way to represent it is sum_square(xi - x), but it also needs proper linearization before feeding to MILP solver.
I would really appreciate your help or suggestions.
Many thanks,
Kaitai
Please tell us the problem more precisely. What are the decision variables, and what are the constants/parameters?
Hi Adam,
Apologise for the unclear questions. So here is the whole picture of the issue I have now.
So I have a list of tasks to examine over a number of exams (see matrix.png). And 0 means no examination and 1 means require examination. This 0/1 can be formed into a matrix A. And each task takes certain hours (see matrix2.png). So for each examination, the total hours needed can be calculated by x = AT * h.
With the goal of having each exam (column) equal the same amount of time, we are able to move tasks to different exams to get the best plan. The only direction we can move a task is to a lower exam (column), not higher. So if task 1 appears in exam 4, it can go to exam 1,2,3. And each entry can only be 0 or 1.
To find the best solution, I have to minimize the difference between the sum of hours of each column, which leads to min sum (|xi - xj|).
And i wonder how to linearize this objective so that it can be nicely fit into an MILP or MIP problem solver.
I hope this is more clear. Please let me know if you are confused and thank you for your time for helping out!
Many thanks,
Kaitai
For each task t and each exam e, let x_{te} be a binary variable, taking the value 1 if and only if task t is covered by exam e. For each exam e, let y_e be a non-negative continuous variable, representing the duration of exam e. For each pair e, f of exams, let z_{ef} be a non-negative continuous variable, representing the difference between y_e and y_f. Hopefully the objective and constraints will be pretty obvious.
Adam N. Letchford
Hi Adam, thanks for replying to me. I get the part where you represent the matrix with x_{te}, but in the end you use z_{ef} to represent the objective, and it is basically taking the absolute value of the y_e - y_f. But still this min sum z_{ef} needs to be linearised for the objective function so that it can be used in the MILP solver. Can you please elaborate a bit on this? And how can I define the constraint where I can only move the exam forward?
thank you so mu for helping out and explaining to me!
Kaitai
Just add the constraints z_{ef} >= y_e - y_f and z_{ef} >= y_f - y_e. And delete the x variables that you don't want to use.
Hello Adam,
Sorry for the silly question, but why should I delete unused x variable? the idea is to have a constraint that only move the examinations forward. But deleting the x variable will change the size of matrix And it cannot achieve the constraint
Saying that you can only move tasks forward is equivalent to setting some x variables to zero.
Adam N. Letchford sorry to bother you again, I am a bit struggling to put it into a mathematical form. So I have summarized the optimisation process in the attachment. Here I have listed the objective and a number of constraints. However, I am unsure how to convert the moving forward condition into mathematical formula. Can you please shed some light on it? Also, I am very new to this problem, I wonder what type of MILP problem can be categorized into?
Dear Calvin,
You are missing a lot of details.
First, you need to define some index sets. E.g., let E be the set of exams and T be the set of tasks. For each exam e in E, let T(e) be the set of tasks that can be examined in exam e. And so on.
Second, you need to add some more constraints. For example, for each exam e in E you need
y_e = \sum_{t \in T(e)} h_t x_{te}.
I recommend reading a textbook on mathematical programming formulations. The one by H.P. Williams is very good.
The whole model will be a mixed 0-1 linear program, since it has a mixture of continuous and 0-1 variables.
Adam N. Letchford Hi Adam, thank you very much for point a way for me. I have modified a number of things and attached the new form of equations in this conversation. I am still unsure how to add the 'move forward' constraint in it. Because x_{t,e} has original form and then i want to check and make sure the 1s in the optimised x_{t,e}^{opti} can only be the same or forward position as the original x_{t,e}. Any suggestions on the equation will be truly appreciated! Again, thank you a lot for your patient guidance!
Here is the full formulation. (I assume that you know the LaTeX syntax for equations.)
INDEX SETS:
Let E be the set of exams and T the set of tasks.
For each e in E, let T(e) be the set of tasks that can be covered by exam e.
For each t in T, let E(t) be the set of exams that can cover task t.
CONSTANTS:
For each t in T, let h_t be the time taken to do task T.
VARIABLES:
For each task t and each exam e in E(t), let x_{te} be a binary variable, taking the
value 1 if and only if task t is covered by exam e.
For each exam e, let y_e be a non-negative continuous variable, representing
the duration of exam e.
For each pair e, f of exams, let z_{ef} be a non-negative continuous variable,
representing the difference between y_e and y_f.
OBJECTIVE:
\min \sum_{\{e,f\} \subseteq E} z_{ef}.
CONSTRAINTS:
Each task must be covered by one exam:
\sum_{e \in E(t)} x_{te} = 1 (\forall t \in T).
Duration of exams:
y_e = \sum_{t \in T(e)} h_t x_{te} (\forall e \in E).
Differences between durations:
z_{ef} \ge y_e - y_f (\forall e \in E, f \in E \setminus \{e\}).
This is for specialized discipline. I am a lawyer and psychologist.
- Badges
- Science topic
- Similar topics
- Methodology
- Research Methodology
- Research Papers