Geek Answers Handbook

How to check, without an object function, if restrictions are possible?

My professor gave me the binary linear programming problem, but this problem is slightly different from the optimization problems that I used to solve (i.e. this is probably not maximizing or minimizing the function of the object.)

The problem is the following: For the matrix M, for the records m_ij! = 0, there are corresponding variables x_ijk. The entries m_ij = 0 can be ignored.

x_ijk is either 0 or 1, and I want to try 5 x_ijk variables for each m_ij (that is, x_ij1, x_ij2, x_ij3, x_ij4 and x_ij5. One of them is 1 and the rest 0) satisfy some conditions (set of inequalities).

Simply put, it is to check whether a set of constraints, including 5 x_ijk variables for each m_ij, are permissible (or permissible) constraints.

I solved some optimization problems, but I never solved the problem without an objective function.

What should I set as my objective function here? 0? nothing?

I could use lp_solve or CPLEX.

Thank you in advance for your advice!

+4
source share
1 answer

That's right, you can set an arbitrary constant value as an objective function.

Most of the solvers I've tried allow an empty objective function. Just leave it out of your model.

Depending on the solver and the API that you use, it may happen that you need to set the coefficients of all variables in the object to zero.

Do not worry, it should work.

In response to your comment: Yes, constraint programming tools can provide better performance on feasibility issues than LP solvers (like CPLEX). I played several times with IBM ILOG CPLEX CP Optimizer , it's free for academic users. The solver LP and the solver CP did not cope with my problems. Do not expect the miracle of programming restrictions.

Keep in mind that the time required to solve a constraint program grows exponentially with the size of the problem in the worst case. Sooner or later, your problems will most likely become unsolvable with any tool.

Just for your information: in the end, the constraint programming solver will call the LP solver (like CPLEX).

My advice: try the tool that you already have / use the wording of the problem that is more natural for you. Check if the tool can solve your problem. Switch the tool only if the tool fails and you cannot improve your model.

+4
source

More articles:


All Articles