3
$\begingroup$

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\}$

Motivation

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.

  • 0
    Can $g_c(\textbf{x})=1$ for other cliques of variables in $\textbf{x}$?2011-07-27
  • 0
    $g_c(\mathbf{x}_c)$ is only defined on the clique $c$. There can be several $g_c$ for different cliques.2011-07-27
  • 0
    Then wouldn't $y_i = g_c(\textbf{x}_C)$ work?2011-07-28
  • 0
    @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.2011-07-28
  • 0
    @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.2011-07-28
  • 0
    If all you want is $y_i = g_c(\textbf{x}_c)$ using linear inequalities, wouldn't the two inequalities $y_i \leq g_c(\textbf{x}_C)$ and $y_i \geq g_c(\textbf{x}_C)$ together work? Tightening the inequalities will probably depend on the form of the functions $g_c$; I'm not sure there's much to say without knowing what those are.2011-07-28
  • 0
    @Mike, if $g_c$ is a generic boolean function, how would get, for example, **linear** inequalities? E.g. Say $g_c(x_1,x_2,x_3,x_4) = (x_1 + x_2) (x_1 + x_3)(\lnot x_2 + \lnot x_2 +\lnot x_4)$. $g_c$ is not linear in the variables in the clique, so the inequalities $y_i \le g_c(\mathbf{x}_c)$ and $y_i \ge g_c(\mathbf{x}_c)$ would not be linear in the variables.2011-07-28
  • 0
    I didn't realize $g_c$ could be nonlinear. Obtaining linear constraints with a generic nonlinear function - that sounds really nasty, and I don't know how to do it. In fact, my guess is that it's not possible (although I would be happy to be proved wrong).2011-07-28

0 Answers 0