2
$\begingroup$

I have a linear program, where I can use it with the same constraint to minimize objective 1 or minimize objective 2. I noted that when I use the formula of objective 2 the problem can be solved with large instances in polynomial time whereas when I use objective 1 that takes a long time for medium instance. When that can occur?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
1
$\begingroup$

It is not uncommon that with different objective functions, there are different complexity that comes with the specific problem. For example, in the scheduling theory, it is often of interest to determine the borderline between polynomial-time problems and NP-hard problems. In order to determine the exact boundaries, it is necessary to find the “hardest” or the “most general” problems that still can be solved in polynomial time. These problems are characterized by the fact that any generalization, e.g., the inclusion of precedence constraints, results in NP-hardness, either in the ordinary sense or strongly.

For comparison, in the following, there are three different classes of the problem and their specific solvable complexity:

  • $\text{1} \ | \ r_j, p_j=1, prec \ | \ \sum{C_j} $
  • $\text{1} \ | \ r_j, prmp \ | \ \sum{C_j} $

are Polynomial-Time Solvable Problems while:

  • $\text{1} \ | | \ \sum{w_jU_j} $
  • $\text{1} \ | | \ \sum{T_j} $

are NP-Hard in the Ordinary Sense and:

  • $\text{1} \ | s_{j,k} | \ C_{max} $
  • $\text{1} \ | \ r_j \ | \ \sum{C_j} $

are Strongly NP-Hard Problems.

The above examples obviously turn out that, changing the objective functions can significantly change the solving time, specifically, if one would like to use multi-objective optimization.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Very nice thank you, but in your example, you can see that the constraints you use at each LP are changed, whereas in my problem the constraint is the same we change only the objective function( for example one minimize the time and the other minimize the cost while keeping the same constraints) that is logical? $\endgroup$
    – MAJID majid
    Dec 11, 2021 at 9:34
  • $\begingroup$ @MAJIDmajid, you're welcome. Actually, it is not. In some problems I mentioned, the constraints are the same, and the only things that have been changed are the objective functions. $\endgroup$
    – A.Omidi
    Dec 11, 2021 at 10:28
  • $\begingroup$ So, what do you suggest for me? i am not familiarised with combinatorial optimization $\endgroup$
    – MAJID majid
    Dec 11, 2021 at 10:36
  • 1
    $\begingroup$ @MAJIDmajid, it really depends on the problem you have faced. In the community, you can find many related posts and questions on how one would be capable to solve an optimization problem faster. In some cases by changing the formulation, for others by using advanced methods like decomposition and etc. :) $\endgroup$
    – A.Omidi
    Dec 11, 2021 at 12:41
  • $\begingroup$ Thank you, please in the example you give how they prove the solvable complexity? $\endgroup$
    – MAJID majid
    Dec 11, 2021 at 18:40
2
$\begingroup$

Draw a unit circle around the origin in $\mathbb{R}^2$ and consider the quarter of it in the first (nonnegative) quadrant. Now pick a large number of points on the circle and make them, along with $(0,0)$, $(0,1)$ and $(1,0)$, the corner points of your feasible region.

Now, starting at the origin, count the number of corner points you need to pass through to maximize $x_1 + x_2$ (a bunch) and the number of corner points you need to pass through to maximize $x_2$ (one). Each corner visited is one pivot of the primal simplex algorithm.

If it takes a large number of pivots to reach the optimum for one objective, you might try an interior point method, which might (or might not) be faster.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Sorry, I didn't understand your meaning. I am a beginner with combinatorial optimization. $\endgroup$
    – MAJID majid
    Dec 11, 2021 at 9:35
  • $\begingroup$ If the objective is to maximize $x_2$, the simplex method starts at the origin, does one pivot, arrives at (0, 1) and is done. If the objective is to maximize $x_1 + x_2$, the simplex method starts at the origin, move to either (0, 1) or (1, 0) (the choice is arbitrary), continues moving through points you picked and eventually arrives at the points you selected closest to $(1/\sqrt{2}, 1/\sqrt{2})$. $\endgroup$
    – prubin ♦
    Dec 12, 2021 at 1:35
  • $\begingroup$ Since each pivot moves from one corner point to an adjacent corner point, the number of pivots required to get to the optimum will be the number of points you picked between the best solution and the first place simplex moved. Conclusion: the objective function affects the number of pivots. $\endgroup$
    – prubin ♦
    Dec 12, 2021 at 1:35
  • $\begingroup$ thank you understand now. Now I see by experimentation that my linear can be solved in polynomial time for F2 and takes a very long time when we make F1, how can I prove that for F2 my linea program is solved in polynomial time? or just by experimentation? $\endgroup$
    – MAJID majid
    Dec 12, 2021 at 11:39
  • $\begingroup$ Definitely not by experimentation. I don't know how to prove an LP is solvable in polynomial time, unless it reduces to a network model for which there is a known polynomial time algorithm (and then only if you use that algorithm). Perhaps someone else has an answer. If you want to discuss solution time in practice, rather than theoretical complexity, then you can try solving a bunch of problems and see what the time looks like. $\endgroup$
    – prubin ♦
    Dec 12, 2021 at 16:39

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.