Say I have an binary integer programming problem:

\begin{equation*} \begin{aligned} & \underset{\mathbf{x,y}}{\text{minimize}} & & f_0(\mathbf{x,y}) \\ & \text{subject to} & & (\mathbf{x,y}) \in A \\ \end{aligned} \end{equation*} with $(\mathbf{x},\mathbf{y}) = (x_1, \ldots, x_{N}, y_1, \ldots, y_{M}) \in \{0,1\}^{N+M}$

and say I would like to model the set $A$ with conditions such as:

$\quad \quad y_i = 1$ if $g_c(\textbf{x}_C) = 1$ for some clique $c$ of variables in $\mathbf{x}$, where $g_c$ is a boolean function (e.g. a function derived from a truth table using a Karnaugh map).

$\quad \quad y_i = 0$ otherwise.

How would you model a condition like this using linear inequalities, matrix inequalities or second-order cones? Also, how would you progressively tighten their relaxation?

Here is an example of how to model other relationships:

Let's say I want to model a disjunctive constraint on the variables $\mathbf{x}$. Suppose we have two constraints $\mathbf{a'\cdot x}\ge b$ and $\mathbf{c'\cdot x}\ge d$, and we would like to model the requirement that at least one of the two constraints is satisfied using linear inequalities. To achieve this, we can define a binary variable $y$ and impose the constraints:

$\mathbf{a'\cdot x}\ge yb$, $\quad \mathbf{c'\cdot x}\ge (1-y)d$, with $y\in\{0,1\}$


I am interested in using conditional statements to model conditional penalties in the cost function. More specifically, if a solution to my practical problem is given by an assignment to the variables $\mathbf{x}$, I could use the auxiliary variables $\mathbf{y}$ to add conditional penalties when certain conditions are met. For example, I could expand $f_0(\mathbf{x,y})$ as $f_0(\mathbf{x,y}) = f_1(\mathbf{x}) + f_2(\mathbf{y})$, where $f_2(\mathbf{y}) = \sum_{1}^{M}{y_i c_i}$, where $c_i$ are the extra penalties incurred for the configurations of $\mathbf{x}$ declared in the conditional statements.

  • $\begingroup$ Can $g_c(\textbf{x})=1$ for other cliques of variables in $\textbf{x}$? $\endgroup$ – Mike Spivey Jul 27 '11 at 23:18
  • $\begingroup$ $g_c(\mathbf{x}_c)$ is only defined on the clique $c$. There can be several $g_c$ for different cliques. $\endgroup$ – Amelio Vazquez-Reina Jul 27 '11 at 23:20
  • $\begingroup$ Then wouldn't $y_i = g_c(\textbf{x}_C)$ work? $\endgroup$ – Mike Spivey Jul 28 '11 at 2:04
  • $\begingroup$ @Mike, yes. I would like to force that relationship with linear, matrix inequalities, or second-order cones. I'm also interested in how to tighten their relaxation. $\endgroup$ – Amelio Vazquez-Reina Jul 28 '11 at 12:20
  • $\begingroup$ @Mike, to clarify, the original question asked for a solution using linear inequalities only, but I am extending the question to include matrix inequalities or second-order cones. I am hoping that a combination of these helps tightening a relaxation of the variables. $\endgroup$ – Amelio Vazquez-Reina Jul 28 '11 at 12:26

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.