Sum of Max terms maximizationSolver rounding precision vs programming language rounding precisionDifference between lazy callbacks and using lazy constraints directlyMinimizing a project costs through nonlinear optimization
How to befriend private nested class
Is "I do not want you to go nowhere" a case of "DOUBLE-NEGATIVES" as claimed by Grammarly?
String manipulation with std::adjacent_find
Are there any balance issues in allowing two half-feats to be taken without the Ability Score Increase instead of a feat?
LED glows slightly during soldering
Confirming the Identity of a (Friendly) Reviewer After the Reviews
Is English unusual in having no second person plural form?
What questions should I be able to answer when I want to enter the USA on the 4th time?
Switching interface VLAN ID Mid-Production
How are mathematicians paid to do research?
Convert BAM to properly paired FASTQ files
Is it correct to join training and validation set before inferring on test-set?
Why did Harry Potter get a bedroom?
What happened to people in unsafe areas during the Blip?
How can characters/players identify that a polymorphed dragon is a dragon?
Is a request to book a business flight ticket for a graduate student an unreasonable one?
OR-backed serious games
How to know if blackberries are safe to eat
How can a dictatorship government be beneficial to a dictator in a post-scarcity society?
Was I subtly told to resign?
Is anyone advocating the promotion of homosexuality in UK schools?
What happens to unproductive professors?
How to say "How long have you had this dream?"
Is there any reason why MCU changed the Snap to Blip
Sum of Max terms maximization
Solver rounding precision vs programming language rounding precisionDifference between lazy callbacks and using lazy constraints directlyMinimizing a project costs through nonlinear optimization
$begingroup$
Maximizing sum-of-max terms is an NP-hard problem. The objective function is a convex function and maximizing a convex function is a hard problem. Also, this is a non-differentiable function.
CPLEX and GUROBI solve these problems to global optimality. I don't know what method they use. I guess they first eliminate the obviously bad terms in the beginning and then follow a branching tree to optimize each combination. Is this correct? What methods do they use, how can I (roughly) learn about this?
I am interested in linear constraints. For example:
beginalign
beginarrayll
max & leftmax3x_1 + 4x_2 , -2x_1 +7x_2 + max-x_1 + 6x_2 , 5x_1 +3x_2 right \
textst & a leq x_1 + x_2 leq b \
& x_1 geq c, x_2 geq d
endarray
endalign
I am solving a way bigger case.
Edit: Apparently, CPLEX and GUROBI solve Mixed Integer Optimization problems. The equivalent formulation as given in the accepted answer is being generated by YALMIP parser which I use.
solver nonlinear-programming
asked Jul 1 at 21:41
independentvariableindependentvariable
7291 silver badge16 bronze badges
$endgroup$
|
show 1 more comment
$begingroup$
Maximizing sum-of-max terms is an NP-hard problem. The objective function is a convex function and maximizing a convex function is a hard problem. Also, this is a non-differentiable function.
CPLEX and GUROBI solve these problems to global optimality. I don't know what method they use. I guess they first eliminate the obviously bad terms in the beginning and then follow a branching tree to optimize each combination. Is this correct? What methods do they use, how can I (roughly) learn about this?
I am interested in linear constraints. For example:
beginalign
beginarrayll
max & leftmax3x_1 + 4x_2 , -2x_1 +7x_2 + max-x_1 + 6x_2 , 5x_1 +3x_2 right \
textst & a leq x_1 + x_2 leq b \
& x_1 geq c, x_2 geq d
endarray
endalign
I am solving a way bigger case.
Edit: Apparently, CPLEX and GUROBI solve Mixed Integer Optimization problems. The equivalent formulation as given in the accepted answer is being generated by YALMIP parser which I use.
solver nonlinear-programming
asked Jul 1 at 21:41
independentvariableindependentvariable
7291 silver badge16 bronze badges
$endgroup$
1
$begingroup$
could you please add a reference to the hardness result, please?
$endgroup$
– Marco Lübbecke
Jul 1 at 23:39
$begingroup$
Maximizing a convex quadratic form over $Vert x Vert_infty leq 1$ is equivalent to binary quadratic optimization, which is NP-hard (so the problem is "hard" without needing a sum). The asker may have been referring to this.
$endgroup$
– Ryan Cory-Wright
Jul 1 at 23:46
2
$begingroup$
Hi @Ryan, only because this is a special case of a hard problem doesn't make it a hard problem. Google doesn't give me an answer either, maybe I am searching for the wrong terms; this is why I ask for a reference.
$endgroup$
– Marco Lübbecke
Jul 2 at 6:35
$begingroup$
If you allow the sum to have $n geq 1$ terms then isn't the max sum problem a more general version of the hard problem where $n=1$? In any case, I agree that a reference from OP would be nice.
$endgroup$
– Ryan Cory-Wright
Jul 2 at 13:14
2
$begingroup$
Judging from your question on the YALMIP forum, I interpret this as you actually ask how YALMIP models the max operator in a nonconvex setting, i.e. the question is really not about any specific solver, but modelling. The MILP model YALMIP implements is explained on yalmip.github.io/tutorial/logicprogramming/#functions, and it essentially the model described in Ryans answer.
$endgroup$
– Johan Löfberg
Jul 4 at 18:52
|
show 1 more comment
$begingroup$
Maximizing sum-of-max terms is an NP-hard problem. The objective function is a convex function and maximizing a convex function is a hard problem. Also, this is a non-differentiable function.
CPLEX and GUROBI solve these problems to global optimality. I don't know what method they use. I guess they first eliminate the obviously bad terms in the beginning and then follow a branching tree to optimize each combination. Is this correct? What methods do they use, how can I (roughly) learn about this?
I am interested in linear constraints. For example:
beginalign
beginarrayll
max & leftmax3x_1 + 4x_2 , -2x_1 +7x_2 + max-x_1 + 6x_2 , 5x_1 +3x_2 right \
textst & a leq x_1 + x_2 leq b \
& x_1 geq c, x_2 geq d
endarray
endalign
I am solving a way bigger case.
Edit: Apparently, CPLEX and GUROBI solve Mixed Integer Optimization problems. The equivalent formulation as given in the accepted answer is being generated by YALMIP parser which I use.
solver nonlinear-programming
asked Jul 1 at 21:41
independentvariableindependentvariable
7291 silver badge16 bronze badges
$endgroup$
Maximizing sum-of-max terms is an NP-hard problem. The objective function is a convex function and maximizing a convex function is a hard problem. Also, this is a non-differentiable function.
CPLEX and GUROBI solve these problems to global optimality. I don't know what method they use. I guess they first eliminate the obviously bad terms in the beginning and then follow a branching tree to optimize each combination. Is this correct? What methods do they use, how can I (roughly) learn about this?
I am interested in linear constraints. For example:
beginalign
beginarrayll
max & leftmax3x_1 + 4x_2 , -2x_1 +7x_2 + max-x_1 + 6x_2 , 5x_1 +3x_2 right \
textst & a leq x_1 + x_2 leq b \
& x_1 geq c, x_2 geq d
endarray
endalign
I am solving a way bigger case.
Edit: Apparently, CPLEX and GUROBI solve Mixed Integer Optimization problems. The equivalent formulation as given in the accepted answer is being generated by YALMIP parser which I use.
solver nonlinear-programming
solver nonlinear-programming
asked Jul 1 at 21:41
independentvariableindependentvariable
7291 silver badge16 bronze badges
asked Jul 1 at 21:41
independentvariableindependentvariable
7291 silver badge16 bronze badges
edited Jul 4 at 21:41
independentvariable
asked Jul 1 at 21:41
independentvariableindependentvariable
7291 silver badge16 bronze badges
asked Jul 1 at 21:41
independentvariableindependentvariable
7291 silver badge16 bronze badges
asked Jul 1 at 21:41
independentvariableindependentvariable
7291 silver badge16 bronze badges
7291 silver badge16 bronze badges
1
$begingroup$
could you please add a reference to the hardness result, please?
$endgroup$
– Marco Lübbecke
Jul 1 at 23:39
$begingroup$
Maximizing a convex quadratic form over $Vert x Vert_infty leq 1$ is equivalent to binary quadratic optimization, which is NP-hard (so the problem is "hard" without needing a sum). The asker may have been referring to this.
$endgroup$
– Ryan Cory-Wright
Jul 1 at 23:46
2
$begingroup$
Hi @Ryan, only because this is a special case of a hard problem doesn't make it a hard problem. Google doesn't give me an answer either, maybe I am searching for the wrong terms; this is why I ask for a reference.
$endgroup$
– Marco Lübbecke
Jul 2 at 6:35
$begingroup$
If you allow the sum to have $n geq 1$ terms then isn't the max sum problem a more general version of the hard problem where $n=1$? In any case, I agree that a reference from OP would be nice.
$endgroup$
– Ryan Cory-Wright
Jul 2 at 13:14
2
$begingroup$
Judging from your question on the YALMIP forum, I interpret this as you actually ask how YALMIP models the max operator in a nonconvex setting, i.e. the question is really not about any specific solver, but modelling. The MILP model YALMIP implements is explained on yalmip.github.io/tutorial/logicprogramming/#functions, and it essentially the model described in Ryans answer.
$endgroup$
– Johan Löfberg
Jul 4 at 18:52
|
show 1 more comment
1
$begingroup$
could you please add a reference to the hardness result, please?
$endgroup$
– Marco Lübbecke
Jul 1 at 23:39
$begingroup$
Maximizing a convex quadratic form over $Vert x Vert_infty leq 1$ is equivalent to binary quadratic optimization, which is NP-hard (so the problem is "hard" without needing a sum). The asker may have been referring to this.
$endgroup$
– Ryan Cory-Wright
Jul 1 at 23:46
2
$begingroup$
Hi @Ryan, only because this is a special case of a hard problem doesn't make it a hard problem. Google doesn't give me an answer either, maybe I am searching for the wrong terms; this is why I ask for a reference.
$endgroup$
– Marco Lübbecke
Jul 2 at 6:35
$begingroup$
If you allow the sum to have $n geq 1$ terms then isn't the max sum problem a more general version of the hard problem where $n=1$? In any case, I agree that a reference from OP would be nice.
$endgroup$
– Ryan Cory-Wright
Jul 2 at 13:14
2
$begingroup$
Judging from your question on the YALMIP forum, I interpret this as you actually ask how YALMIP models the max operator in a nonconvex setting, i.e. the question is really not about any specific solver, but modelling. The MILP model YALMIP implements is explained on yalmip.github.io/tutorial/logicprogramming/#functions, and it essentially the model described in Ryans answer.
$endgroup$
– Johan Löfberg
Jul 4 at 18:52
1
1
$begingroup$
could you please add a reference to the hardness result, please?
$endgroup$
– Marco Lübbecke
Jul 1 at 23:39
$begingroup$
could you please add a reference to the hardness result, please?
$endgroup$
– Marco Lübbecke
Jul 1 at 23:39
$begingroup$
Maximizing a convex quadratic form over $Vert x Vert_infty leq 1$ is equivalent to binary quadratic optimization, which is NP-hard (so the problem is "hard" without needing a sum). The asker may have been referring to this.
$endgroup$
– Ryan Cory-Wright
Jul 1 at 23:46
$begingroup$
Maximizing a convex quadratic form over $Vert x Vert_infty leq 1$ is equivalent to binary quadratic optimization, which is NP-hard (so the problem is "hard" without needing a sum). The asker may have been referring to this.
$endgroup$
– Ryan Cory-Wright
Jul 1 at 23:46
2
2
$begingroup$
Hi @Ryan, only because this is a special case of a hard problem doesn't make it a hard problem. Google doesn't give me an answer either, maybe I am searching for the wrong terms; this is why I ask for a reference.
$endgroup$
– Marco Lübbecke
Jul 2 at 6:35
$begingroup$
Hi @Ryan, only because this is a special case of a hard problem doesn't make it a hard problem. Google doesn't give me an answer either, maybe I am searching for the wrong terms; this is why I ask for a reference.
$endgroup$
– Marco Lübbecke
Jul 2 at 6:35
$begingroup$
If you allow the sum to have $n geq 1$ terms then isn't the max sum problem a more general version of the hard problem where $n=1$? In any case, I agree that a reference from OP would be nice.
$endgroup$
– Ryan Cory-Wright
Jul 2 at 13:14
$begingroup$
If you allow the sum to have $n geq 1$ terms then isn't the max sum problem a more general version of the hard problem where $n=1$? In any case, I agree that a reference from OP would be nice.
$endgroup$
– Ryan Cory-Wright
Jul 2 at 13:14
2
2
$begingroup$
Judging from your question on the YALMIP forum, I interpret this as you actually ask how YALMIP models the max operator in a nonconvex setting, i.e. the question is really not about any specific solver, but modelling. The MILP model YALMIP implements is explained on yalmip.github.io/tutorial/logicprogramming/#functions, and it essentially the model described in Ryans answer.
$endgroup$
– Johan Löfberg
Jul 4 at 18:52
$begingroup$
Judging from your question on the YALMIP forum, I interpret this as you actually ask how YALMIP models the max operator in a nonconvex setting, i.e. the question is really not about any specific solver, but modelling. The MILP model YALMIP implements is explained on yalmip.github.io/tutorial/logicprogramming/#functions, and it essentially the model described in Ryans answer.
$endgroup$
– Johan Löfberg
Jul 4 at 18:52
|
show 1 more comment
1 Answer
1
active
oldest
votes
$begingroup$
If your problem is reasonably small then one relatively simple approach is to reformulate the objective as a MIP, under a big-M assumption.
Suppose that our objective is to maximize $$sum_i g_i(x),$$ where each $g_i(x):=max_j a_j^itop x+b^i_j$ is the maximum of some affine functions. We can model this by introducing auxilliary variables $theta_i$ such that $theta_i leq g_i(x)$, letting $z_i,j=1$ if the $j$th affine function in $g_i(x)$ is the largest at $x$, and maximizing the following problem:
beginalign*
max quad & sum_i theta_i\
texts.t. quad & theta_i leq a_j^itopx+b_j^i+M(1-z_i,j), forall i, forall j,\
& sum_j z_i,j=1, forall i,\
& z_i,j in 0, 1 , forall i, forall j.
endalign*
The combination of the big-M constraints and "objective pressure" ensures that $theta_i=g_i(x)$ at optimality.
If the problem is larger, the above big-M approach won't give tight enough relaxations for branch-and-bound to perform well and we will need to think about using more complicated formulations. In this case, you should think about exploiting the structure of the problem, i.e., explicitly treating the problem as maximizing the sum of piecewise linear functions.
Tighter formulations than the generic big-M approach have been developed here.
I have no idea whether or not this approach is what CPLEX/Gurobi use.
answered Jul 1 at 22:26
Ryan Cory-WrightRyan Cory-Wright
8254 silver badges17 bronze badges
$endgroup$
add a comment |
Your Answer
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "700"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2for.stackexchange.com%2fquestions%2f860%2fsum-of-max-terms-maximization%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
If your problem is reasonably small then one relatively simple approach is to reformulate the objective as a MIP, under a big-M assumption.
Suppose that our objective is to maximize $$sum_i g_i(x),$$ where each $g_i(x):=max_j a_j^itop x+b^i_j$ is the maximum of some affine functions. We can model this by introducing auxilliary variables $theta_i$ such that $theta_i leq g_i(x)$, letting $z_i,j=1$ if the $j$th affine function in $g_i(x)$ is the largest at $x$, and maximizing the following problem:
beginalign*
max quad & sum_i theta_i\
texts.t. quad & theta_i leq a_j^itopx+b_j^i+M(1-z_i,j), forall i, forall j,\
& sum_j z_i,j=1, forall i,\
& z_i,j in 0, 1 , forall i, forall j.
endalign*
The combination of the big-M constraints and "objective pressure" ensures that $theta_i=g_i(x)$ at optimality.
If the problem is larger, the above big-M approach won't give tight enough relaxations for branch-and-bound to perform well and we will need to think about using more complicated formulations. In this case, you should think about exploiting the structure of the problem, i.e., explicitly treating the problem as maximizing the sum of piecewise linear functions.
Tighter formulations than the generic big-M approach have been developed here.
I have no idea whether or not this approach is what CPLEX/Gurobi use.
answered Jul 1 at 22:26
Ryan Cory-WrightRyan Cory-Wright
8254 silver badges17 bronze badges
$endgroup$
add a comment |
$begingroup$
If your problem is reasonably small then one relatively simple approach is to reformulate the objective as a MIP, under a big-M assumption.
Suppose that our objective is to maximize $$sum_i g_i(x),$$ where each $g_i(x):=max_j a_j^itop x+b^i_j$ is the maximum of some affine functions. We can model this by introducing auxilliary variables $theta_i$ such that $theta_i leq g_i(x)$, letting $z_i,j=1$ if the $j$th affine function in $g_i(x)$ is the largest at $x$, and maximizing the following problem:
beginalign*
max quad & sum_i theta_i\
texts.t. quad & theta_i leq a_j^itopx+b_j^i+M(1-z_i,j), forall i, forall j,\
& sum_j z_i,j=1, forall i,\
& z_i,j in 0, 1 , forall i, forall j.
endalign*
The combination of the big-M constraints and "objective pressure" ensures that $theta_i=g_i(x)$ at optimality.
If the problem is larger, the above big-M approach won't give tight enough relaxations for branch-and-bound to perform well and we will need to think about using more complicated formulations. In this case, you should think about exploiting the structure of the problem, i.e., explicitly treating the problem as maximizing the sum of piecewise linear functions.
Tighter formulations than the generic big-M approach have been developed here.
I have no idea whether or not this approach is what CPLEX/Gurobi use.
answered Jul 1 at 22:26
Ryan Cory-WrightRyan Cory-Wright
8254 silver badges17 bronze badges
$endgroup$
add a comment |
$begingroup$
If your problem is reasonably small then one relatively simple approach is to reformulate the objective as a MIP, under a big-M assumption.
Suppose that our objective is to maximize $$sum_i g_i(x),$$ where each $g_i(x):=max_j a_j^itop x+b^i_j$ is the maximum of some affine functions. We can model this by introducing auxilliary variables $theta_i$ such that $theta_i leq g_i(x)$, letting $z_i,j=1$ if the $j$th affine function in $g_i(x)$ is the largest at $x$, and maximizing the following problem:
beginalign*
max quad & sum_i theta_i\
texts.t. quad & theta_i leq a_j^itopx+b_j^i+M(1-z_i,j), forall i, forall j,\
& sum_j z_i,j=1, forall i,\
& z_i,j in 0, 1 , forall i, forall j.
endalign*
The combination of the big-M constraints and "objective pressure" ensures that $theta_i=g_i(x)$ at optimality.
If the problem is larger, the above big-M approach won't give tight enough relaxations for branch-and-bound to perform well and we will need to think about using more complicated formulations. In this case, you should think about exploiting the structure of the problem, i.e., explicitly treating the problem as maximizing the sum of piecewise linear functions.
Tighter formulations than the generic big-M approach have been developed here.
I have no idea whether or not this approach is what CPLEX/Gurobi use.
answered Jul 1 at 22:26
Ryan Cory-WrightRyan Cory-Wright
8254 silver badges17 bronze badges
$endgroup$
If your problem is reasonably small then one relatively simple approach is to reformulate the objective as a MIP, under a big-M assumption.
Suppose that our objective is to maximize $$sum_i g_i(x),$$ where each $g_i(x):=max_j a_j^itop x+b^i_j$ is the maximum of some affine functions. We can model this by introducing auxilliary variables $theta_i$ such that $theta_i leq g_i(x)$, letting $z_i,j=1$ if the $j$th affine function in $g_i(x)$ is the largest at $x$, and maximizing the following problem:
beginalign*
max quad & sum_i theta_i\
texts.t. quad & theta_i leq a_j^itopx+b_j^i+M(1-z_i,j), forall i, forall j,\
& sum_j z_i,j=1, forall i,\
& z_i,j in 0, 1 , forall i, forall j.
endalign*
The combination of the big-M constraints and "objective pressure" ensures that $theta_i=g_i(x)$ at optimality.
If the problem is larger, the above big-M approach won't give tight enough relaxations for branch-and-bound to perform well and we will need to think about using more complicated formulations. In this case, you should think about exploiting the structure of the problem, i.e., explicitly treating the problem as maximizing the sum of piecewise linear functions.
Tighter formulations than the generic big-M approach have been developed here.
I have no idea whether or not this approach is what CPLEX/Gurobi use.
answered Jul 1 at 22:26
Ryan Cory-WrightRyan Cory-Wright
8254 silver badges17 bronze badges
answered Jul 1 at 22:26
Ryan Cory-WrightRyan Cory-Wright
8254 silver badges17 bronze badges
answered Jul 1 at 22:26
Ryan Cory-WrightRyan Cory-Wright
8254 silver badges17 bronze badges
answered Jul 1 at 22:26
Ryan Cory-WrightRyan Cory-Wright
8254 silver badges17 bronze badges
8254 silver badges17 bronze badges
add a comment |
add a comment |
Thanks for contributing an answer to Operations Research Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2for.stackexchange.com%2fquestions%2f860%2fsum-of-max-terms-maximization%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
$begingroup$
could you please add a reference to the hardness result, please?
$endgroup$
– Marco Lübbecke
Jul 1 at 23:39
$begingroup$
Maximizing a convex quadratic form over $Vert x Vert_infty leq 1$ is equivalent to binary quadratic optimization, which is NP-hard (so the problem is "hard" without needing a sum). The asker may have been referring to this.
$endgroup$
– Ryan Cory-Wright
Jul 1 at 23:46
2
$begingroup$
Hi @Ryan, only because this is a special case of a hard problem doesn't make it a hard problem. Google doesn't give me an answer either, maybe I am searching for the wrong terms; this is why I ask for a reference.
$endgroup$
– Marco Lübbecke
Jul 2 at 6:35
$begingroup$
If you allow the sum to have $n geq 1$ terms then isn't the max sum problem a more general version of the hard problem where $n=1$? In any case, I agree that a reference from OP would be nice.
$endgroup$
– Ryan Cory-Wright
Jul 2 at 13:14
2
$begingroup$
Judging from your question on the YALMIP forum, I interpret this as you actually ask how YALMIP models the max operator in a nonconvex setting, i.e. the question is really not about any specific solver, but modelling. The MILP model YALMIP implements is explained on yalmip.github.io/tutorial/logicprogramming/#functions, and it essentially the model described in Ryans answer.
$endgroup$
– Johan Löfberg
Jul 4 at 18:52