Why don't you simply solve it using branch-and-bound? Use CPLEX solver.

I will check them, Mairton! Thank you.

Anselmo, Branch and Bound works only for low and moderate problem sizes.

It depends on the problem and on your time requirements. Have you already tried it? Don't trust that theoretical excuse that the problem is NP-hard etc... Modern solvers as CPLEX are very fast and reliable. Give it a try. In addition, B & B provides lower and upper bounds on the optimal solution, so that you can stop the search before reaching an optimal solution and you know how far you are from an optimum. Heuristic procedures as rounding cannot give you any guarantees on the quality of the solution. Heuristics is a good choice only if you have very strict time constraints, such as in real-time applications.

I agree with you, Anselmo. And that is exactly the case!

The application is on resource allocation for wireless communication systems. In general, important decisions should be taken every millisecond.

I already use B & B from CPLEX. I am a big fan of this tool.

You might find interesting and solve your problem by examining the following papers in Research Gate:

Any integer linear program (ILP) or more general any combinatorial linear programme may be set up as a Linear Complementarity problem which may be solved by a Linear Programme if a set of conditions regarding the  structure of the problem are satisfied. This was proved by O.L. Mangasarian (1979). Further it may be shown that these sets of conditions may be imposed in the linear programme without altering the feasability or the solution set of the problems. So you can solve an ILP problem by solving an LP.  To see how this is done examine 3 below and Mangasarian's theorem. To have an inkling on how well this approach performs have a look at 2. As a first approach I would suggest that you examine 1.

I am of course at your disposal if you wish to have more information and explanations of how to solve problems by this technique.

Yours Very Sincerely,

Giacomo Patrizi

Conference Paper: SOLVING COMBINATORIAL PROBLEMS as formulations of Linear Complementarity Problems

Giacomo Patrizi

[Show abstract]

paper presented at C.O.R.E (Center for Operations Research and Econometrics, Universite' Catholique de Louvain, Belgium, Universite' Catholique de Louvain, Belgium; 02/2009

Article: Linear Complementarity as a General Solution Method to Combinatorial Problems

Laura Di Giacomo · Giacomo Patrizi · Emanuele Argento

[Show abstract]

Informs Journal on Computing 02/2007; 19(1):73-79. DOI:10.1287/ijoc.1050.0146 · 1.12 Impact Factor

Article: The equivalence of an LCP to a parametric linear program with a scalar parameter

Giacomo Patrizi

[Show abstract]European Journal of Operational Research 02/1991; 51(3):367-386. DOI:10.1016/0377-2217(91)90312-J · 1.84 Impact Factor

Not sure if this is significant but in constraint#1, what is the subscript on a in the constraint (a_np) ?? should that be a_jp? If it is a_np, can you preprocess the cases (since you say it is binary). Have you worked on any relaxation of that constraint?

Thank you Mr. Patrizi. I will check your work and if needed I will contact you.

Mr. O'Kelly: The correct is a_np. "n" is another independent index. I do not understand what you mean by "preprocess" and "relaxation of the first constraint".

Dear Francisco,

thank you for your evaluation and I hope to be of help.

In the material provided, you will find examination of the solutions by the algorithm proposed and particular heuristics of a number of problems.

Branch and Bound algorithms has been proved to be an algorithm ( an algorithm is an efficient procedure which will provide the solution of the problem  or indicate that no such solution problem can exist). In this regard you can examine the satisfiability problem solutions in  the  papers and in the references, where B.B. solution implementations are examined and will converge usually to a solution, unless the subproblems to be solved become too large and swamp the machine's capability.

CPLEX is a well known heuristic and therefore must not be considered an algorithm since short cuts (often propriety) are enacted so it is not known if it will solve the problem, determine that no solution will exist, or  get lost because of the effect of short cuts. To examine some results look at  paper (2)  table 2, table 3 and 4.

In table 2  at the time XPRESS was a routine analogous to CPLEX  and can be compared to the precise LCP solutions, where the time to solve these problems depends on the size of the problems while XPRESS and the CPLEX routines in table2, 3 and 4 are extremely unstable depending if the short cut helps or not, so these must be considered good guesses but guesses nevertheless.

In table 3  you will find the problems with many vehicles so the problems are relatively unconstrained and in table 4 the same problems are severely constrained. The effect on CPLEX is dramatic!

Friends and colleagues call me Jacopo and not  Giacomo  Patrizi, may I consider you in the group?

Yours

Jacopo

Even outer approximation branch and bound method in bonmin algorithm(B-OA) can be used in ampl environment.

Dear Mahamad Nabab  Alam

I am not familiar with this code, but I will look at it and provide eventually a more detailed analysis if desired.

From the bonmin fact sheet two contradictions or limitations are immediately apparent:

(a) Francisco proposed an Integer linear problem so the objective function and the constraints are only once continuously differentiable, at best, and not twice continuously differentiable as demanded in the code sheet. You should study the code to determine its effect on the convergence and the number of iterations that will arise.

(b) Functions defined over non continuously spaces, as in the case of mixed integer problems cannot be convex over the space since they will not satisfy the definition of a convex function and will not be continuous in the space.

So for such problems as indicated by Francisco,  the solution determined with this code is certainly not exact (however it is defined, by their admissions in the fact sheet) and so bonmin must be considered for such problems a heuristic  with all the usual limitations: lack of convergence and lengthy running times to find perhaps the correct solution.

I hope that I have been of help,

Yours Very Sincerely,

Giacomo Patrizi

Dear Mahamad Nabab  Alam

I am not familiar with this code, but I will look at it and provide eventually a more detailed analysis if desired.

From the bonmin fact sheet two contradictions or limitations are immediately apparent:

(a) Francisco proposed an Integer linear problem so the objective function and the constraints are only once continuously differentiable, at best, and not twice continuously differentiable as demanded in the code sheet. You should study the code to determine its effect on the convergence and the number of iterations that will arise.

(b) Functions defined over non continuously spaces, as in the case of mixed integer problems cannot be convex over the space since they will not satisfy the definition of a convex function and will not be continuous in the space.

So for such problems as indicated by Francisco,  the solution determined with this code is certainly not exact (however it is defined, by their admissions in the fact sheet) and so bonmin must be considered for such problems a heuristic  with all the usual limitations: lack of convergence and lengthy running times to find perhaps the correct solution.

I hope that I have been of help,

Yours Very Sincerely,

Giacomo Patrizi

Is there an efficient and aproximative rounding algorithm for the problem below? - ResearchGate. Available from: https://www.researchgate.net/post/Is_there_an_efficient_and_aproximative_rounding_algorithm_for_the_problem_below [accessed Sep 20, 2015].

since the problem is integer programming problem, instead of using rounding algorithm  using branch and bound or metaheuristic algorithms perform better than rounding

Dear Adugna Fita,

I have tried to answer fully to your mail, but the system short circuited my reply and I do not know if you have received it.

Let me summarize its content in this way.

If the problem considered is an integer (preferably binary) linear problem of large dimensions then solve the problem as an linear programme with bounded variables as needed and if there are still some variables that should be binary which are fractional then discretize these values. This will be more efficient than using branch and bound or metaheuristics routines, depending on the number of fractional values in integer variables. For proof of this statement see:

Lasdon, Leon. S., Optimization Theory for Large Systems. Macmillan, New York City, 1970 (reprint Dover, New York City, 2002) and the references provided.

In mathematics it is always very dangerous to jump to conclusion. It is important to study the type of problem considered, examine the scientific material and try to prove your affirmations. This is important, because you might want to consider a problem which is non linear and is of limited dimensions,  then one of the way to solve it could be branch and bound and a metaheuristic.

Finally, any branch and bound procedure is enacted through sequential discretization, that is by rounding! To see this:

- set up your problem as a linear programming problem (LP) and solve it

- if the solution has one or more fractional integer variables, define for the first fractional integer problem two rounded LP one by constraining that variable at its lower discrete value and the other problem at its higher discrete value and solve these two LPs.  and continue by Branch and Bounding.

Branch and Bound techniques are therefore sequential discretization procedures and under general conditions convergence (to the optimal solution) can be proven,

Metaheuristics are based on heuristics and therefore usually have a certain content of guess work, so no convergence proofs can be provided.

Glad if these considerations are of help and please let me know if I can be of help.

Yours Very Sincerely,

Giacomo Patrizi

It looks like a set partitioning problem.  It is well known that the problem of checking whether a set partitioning problem has a feasible solution is NP-complete.  Therefore, no approximation algorithm can exist.  On the other hand, there exist several excellent exact algorithms for the set partitioning problem, that can solve instances with hundreds of thousands of variables and hundreds of constraints.  See, e.g., the works of David Ryan, Karla Hoffman or Ralf Borndoerfer.

Dear Adam,

the problem posed may be a set partitioning problem, but this should be confirmed by its proposer

The formal definition of a process called an algorithm is the following:

" An algorithm is an effectively computable process that terminates or is blocked." see:

Curry, H., B., Foundations of Mathematical Logic, McGraw-Hill Book Co. Inc. New York, 1963, pp. 70--81.

Markov, A., A., Teoriya algorifmov (Theory of Algorithms), Trudy Mat.Inst. Steklov, 38: 176-189 (1951); English translation by Edwin Hewitt in American Mathematical Translations, ser. 2, 15: 1-14 (1960)

Davis, Martin, Computability and Unsolvability, Dover Publications, New York , 1982 (1958).

Given this definition an 'approximation algorithm' is a logical contradiction: a process is either approximate or is an algorithm. Further the term 'exact' is confusing since any algorithm must be considered exact.  The existence of an algorithm for a set partitioning problem confirms Lasdon's result  even if limited to particular instances, and so will those algorithms of the works indicated.

It might have been desired to use a more general definition of an algorithm, say by stating that it is purely an effective computable process,   however it will terminate or however is blocked. In this looser version of 'algorithm'  approximation algorithms exist by definition as is immediate, so will several excellent exact algorithms but this would contradict your assertions. Obviously with this understanding by reducing sufficiently the acceptable approximation level at some point the process exists, if your second assertion is accepted, but that would contradict your first assertion.

The NP-complete theory is considered well founded and it is easy to resolve the confusion that has arisen, because of an unfortunate use of a precise term interpreted in two contradictory senses which introduce the apparent ambiguities destroying the scientific character of mathematical processes.

Dear Giacomo,

I was using the term "approximation algorithm" in the sense currently used by the theoretical computer science and operational research communities.  See:

https://en.wikipedia.org/wiki/Approximation_algorithm

Approximation algorithms in this sense can be developed only for optimisation problems for which it is easy to find a *feasible* solution.  For this reason, you will find papers that present approximation algorithms for the set packing and set covering problems, but not for the set partitioning problem.

Hope that helps to clarify things.

Regards,

Adam.

Dear Adam,

it would be very surprising if there were great differences in the conception of processes (algorithms) in mathematics or in Computer Science, which are not, but purely differences in the precision of the termination or blockage criteria, see:

Korte, B., J. Vygen, Combinatorial Optimization Theory and Agorithms, Springer, Berlin , 2012 (5th edition) especially chapter 16.

So all the limitations and logical contradictions  indicated previously  and the answers to Francisco's and others questions stand. 

The choice regarding which routine should be used depends on the conditions that the problem must hold. For instance, if the problem is ILP and the conditions of the theorem of Mangasarian (see above) are satisfied then a linear programme can be used to solve the problem as described etc.

Which  routine should be selected? This will depend on the characteristics that can be proven to apply and are logically consistent,  not on hearsay or on rules of thumb if these can be avoided.  In dire cases a good guess or some convenient heuristic may be helpful, but it must be supposed that no proof of the correctness of the result  can be  proposed. It should be ensured however that even in this case logical contradictions do not occur in the implementation as otherwise the result will be nonsensical.

This should return the focus on the question asked by Francisco and the others and I am available to develop these general conclusions further  if is desired and even other specific  points  which you might like to examine.

Yours Very Sincerely,

Jacopo