4
$\begingroup$

I am trying to solve a two dimensional combinatorial problem. Hereis my input space {{RA1,RA2},{RB1,RB2},{RC1,RC2}} and i have to choose two out of three elements{A,B,C} and one out of two possible variations for each of these elements {1,2}. I have an objective function to maximize and i have some constraints. Based on these i have to make above selections. Can anyone please tell me if there is any optimization algorithm already available which serves my purpose. In reality i have a huge input space, so any existing algorithm is prefered

$\endgroup$
1
$\begingroup$

Sure, try integer linear programming. Let $x_{RA1}$ be a zero-or-one variable that is 1 if you select RA1, or 0 if you don't. Then each of your constraints can be expressed as linear inequalities with these variables. You can then try applying an off-the-shelf ILP solver.

There are a bunch of other questions on this site with further examples of using ILP to solve combinatorial problems (e.g., Express boolean logic operations in zero-one integer linear programming (ILP)), so feel free to look around.

$\endgroup$
  • $\begingroup$ Thank You D.W. Can you point me to any existing python packages which provide the solver. I was planning on using cvxpy but i have been running into installation issues. I am receiving 'ModuleNotFoundError: No module named 'cvxpy.expressions.variables' error. I am solving an optimization problem for the first time, hence the hiccups. Any help is greatly appreciated. $\endgroup$ – Jiterika Jul 26 '18 at 20:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.