0
$\begingroup$

Integer Programming formulation described as follows:

Assume a set of variable $V$ = ${v_1,...,v_m}$.

The set of total $S$ constraints is of the form:

$$v_1 + \overline{v_2} + v_3 \leq 1 \\ ... \\ \overline{v_2} + v_4 + v_6 \leq 1 $$

each called a clause, $C$.

Problem formulation (Objective function):

Find an assignment that satisfies maximum constraints (out of S constraints).

Formally: $$r(C) = max \sum_{C \in S} z_{C}$$

The variable $z_C$ will be 1 if the each corresponding constraint is true; for example in case $v_1 + \overline{v_2} + v_3 \leq 1$ is true and 0 otherwise.

I'm new to Integer programming and first tool that I tried MIP solver I can write all $S$ constraints easily. But I have no idea how to encode the objective function.

$\endgroup$
1
  • $\begingroup$ Note that you can replace any appearance of $\overline{v_u}$ with $1-v_u$. $\endgroup$
    – RobPratt
    Dec 31, 2019 at 18:54

1 Answer 1

Reset to default
1
$\begingroup$

The objective function to be maximized is $\sum_{C\in S} z_C$. You can define it here.

$\endgroup$
2
  • 1
    $\begingroup$ You can represent the "such that" part by defining constraints. $\endgroup$
    – RobPratt
    Dec 31, 2019 at 18:18
  • $\begingroup$ No problem. I recommend working through that complete example and modifying it. $\endgroup$
    – RobPratt
    Dec 31, 2019 at 18:27

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .