I have a particular research problem that I'm formulating as a linear program. It's more or less an instance of the transportation problem, except there is one additional constraint that is proving difficult to translate into the canonical form required by LP solvers. The constraint is $$ \sum\limits_{i'=i+1}^k \sum\limits_{j'=j-1}^1 x_{i' j'} + \sum\limits_{i'=i-1}^1 \sum\limits_{j'=j+1}^n x_{i' j'} \leq (k+1)(1-x_{ij})\,\forall i,j $$

Is there a general method of converting these constraints into a form that a standard LP solver accepts? Thanks in advance for help or advice.

  • $\begingroup$ This is a programming question, and so off-topic here. Just calculate the coefficient of each variable in each constraint. $\endgroup$ – Yuval Filmus Apr 11 '16 at 22:12
  • $\begingroup$ Did you ever take a class on LPs? They usually cover canoncial forms and how to get there. $\endgroup$ – Raphael Apr 11 '16 at 22:12
  • $\begingroup$ Is this a pure mathematics question that should be migrated? Community votes, please! $\endgroup$ – Raphael Apr 11 '16 at 22:13
  • $\begingroup$ Plus, what Yuval says: the input particularities of software artifacts are offtopic here. If you can specify the form you need to obtain, you may get an ontopic question. $\endgroup$ – Raphael Apr 11 '16 at 22:14
  • $\begingroup$ No, my experience with LPs is only on the theoretical end. I'll edit to add the canonical form we need. $\endgroup$ – pg1989 Apr 11 '16 at 23:14

Your Answer

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

Browse other questions tagged or ask your own question.