8
$\begingroup$

I would like to linearize a constraint with max. I have the following constraint:

$$\max_{pcj}X_{pwcj}\leqslant L_{wk}.$$

With this constraint, I would like to ensure that for $\forall w \in W$, no matter the values of $p$, $c$ and $j$, the max value of the decision variable $X_{pwcj}$ must be less than or equal to the value of the decision variable $L_{wk}$.

  1. How can I linearize this function? I've seen some examples, such as How to linearize a constraint with a maximum of binary variables times some coefficient in the right-hand-side. However, their decision variable has only one index. In my case, I have 4 indexes and $w$ must be fixed at each time.

Actually, I would like to check for each set of $w$ occurrences in a sequence given by $j$:

$$H_w=\max \{X_{pwcj}, X_{pwcj+1},\ldots, X_{pwcn}\}$$

I was wondering what the best way to write my constraint could be:

$$H_{w}\leqslant L_{wk}$$ where $n$ is the max number of $j$ positions, but I am not sure.

  1. If I use this notation, I think that I could do something like this: How to formulate (linearize) a maximum function in a constraint? proposed by @LarrySnyder610, however, in my case I have a set of the same variables thus I am not sure that I can do this.

If this notation can be used in my case, could I ignore the big M value, since both of my variables are binary?

Could someone help me with these questions?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
10
$\begingroup$

Welcome to OR.SE! If you're looking to enforce $$\max\limits_{pcj}X_{pwcj} \leq L_{wk}, \ \forall w,k$$ then simply using the constraint $$X_{pwcj} \leq L_{wk}, \ \forall p,w,c,j,k$$ will do the trick. This will ensure every value (including the maximum) will be at most $L_{wk}$.

(If there's another dynamic you're looking to enforce, e.g., within a set of occurrences, could you clarify/add some more detail to your question?)

Improve this answer
$\endgroup$
4
  • $\begingroup$ Hello @Tucker. Thanks for your reply. I will try to give more explanations. My problem is related to the process planning and machine layout position. X=1 if an operation p is accomplished by a machine w with configuration c at process plan position j. No matter how many times a given machine appears on the process plan, this machine w will be placed in only one layout location k, so Lwk =1. In this case, I think that I most stablish a relation of the max X for all w with the L value. What do you think? $\endgroup$
    – campioni
    Oct 3, 2019 at 13:20
  • $\begingroup$ @campioni, thank you for the additional detail. Is the purpose of the constraint to ensure that $X$ is forced to 0 if $L =0$ for that machine (i.e., can't use machine if not located anywhere)? If not, what is the relationship you are trying to establish between $X$ and $L$? $\endgroup$
    – E. Tucker
    Oct 3, 2019 at 14:18
  • 1
    $\begingroup$ thank you again for responding rapidly. Actually, I was trying to ensure that for all occurrences of a given machine on the process plan, it will be placed in just one layout stage. However, I realized I am ensuring that with another constraint, which states that each machine can be placed in just one layout stage at time. Thus the constraint you suggest me, ensures the relation you said ("can't use machine if not located anywhere"). I was complicating something simple. Thank you so much for your help! $\endgroup$
    – campioni
    Oct 3, 2019 at 15:06
  • $\begingroup$ Happy to! Glad it was helpful. $\endgroup$
    – E. Tucker
    Oct 3, 2019 at 15:46
-1
$\begingroup$

There are some nice topics on linearization of MAX/MIN/ABS functions in LPs/MIPs. Would you see the following links by @prubin and C. Coelho? I hope, they will be useful.

Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ Perhaps you could summarize under each bullet? Otherwise this leads to the classic your answer is in another castle issue. As links rot, this answer's value would diminish. $\endgroup$
    – SecretAgentMan
    Oct 8, 2019 at 0:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.