Search code examples
cplexdocplex

Find initial feasible solution for all agents

EDIT for a better explanation (I'm sorry).

I have a semi-decentralized optimization problem. By semi-decentralized I mean: I have an aggregator that controls the best response for each agent, but those agents have an individual cost function (the variables and constraints are replicated for all of them). Theoretically, I just need to find an initial feasible point (for all agents), and then by solving the optimization problem for each agent iteratively, it converges to an optimum.

My problem here was that, in order to find an initial feasible point, I don't consider every agent at the same time, but rather use the iterative cycle for the optimization phase without an objective function (with mdl.remove_objective). I thought, that by running it enough times, it would eventually arrive at a feasible solution for all agents. However, the solutions that CPLEX arrives at, are all pretty similar. This makes that there is no possible feasible solution for the 6th agent, no matter how many times I run it.

My question here is: How can I impose that at each iteration the feasible point is an actual random point inside the feasible set? Because it looks like, maybe from the shortcuts that CPLEX uses to find a feasible solution, it chooses always a similar solution.

(I know that I can just solve for the initial feasible point with all agents at the same time, but I am still interested in knowing if it is possible to do what I wanted to)

Thank you!

Solution

  • Two ideas:

    • for one given model instance, you might try Model.populate_solution_pool which returns a pool of solutions.
    • second, if the objective does not really matter, but you want to explore the feasible solution space in different directions, you might try to set different "random" objectives in each run. CPLEX is designed to find optimal solutions for an objective; therefore setting the objective is the way to "drive" cplex to look for solutions in different directions. For example, generate a subset of binary variables, compute the sum and try maximize this sum (or anything more appropriate in your case.)

    This said, it may also happen that your problem is so tight that not many solutions exists, and CPLEX always falls back on the same solutions. If CPLEX logs show very few solutions found with different objectives, then you'll know this is what happens.

    Lastly, setting mip emphasis parameter to 1 (feasibility) or 4 (hidden feasibility) might help to favor feasibility over optimality.