Questions on optimization constrained to integer variables.

learn more… | top users | synonyms

0
votes
0answers
12 views

How to find the analytical solution of this optimization problem?

I have an optimization problem of the form $$\begin{align} \text{maximize}\quad&\sum_{i=1}^{k}\sum_{j=1}^{n}w_{ij}x_{ij}\\\text{s.t.}\quad \quad\quad\,\,& \sum_{i=1}^{k}x_{ij}\leq 1,\;\forall ...
0
votes
0answers
17 views

Sensitivity analysis on zero-one Knapsack problem

I have a zero-one Knapsack problem as follows: $$\max \sum_i e^i x_i+\sum_j f^j y_j$$ $$\text{s.t.} \quad p\sum_i x_i+c\sum_j y_j \leq b$$ $$x_i, y_j \in\{0,1\} \quad \forall \ i,j$$ where $e$ and $...
3
votes
2answers
105 views

Find all solutions to $2 x + 3 y + 4 z = 10$

I do not have a background in math, and am wondering what type of question this is. I looked combinatorics optimization, and the knapsack problem, but found the vocabulary too dense. The problem: ...
0
votes
1answer
12 views

Formulating a problem involving sets with ILP

Consider set $\mathcal{G} = \{G_1, \ldots, G_K\}$. We are given $\mathcal{A}_i \subset \mathcal{G}$, $i \in \mathcal{N}= \{1,\ldots, N\}$ and for each $\mathcal{A}_i$, there is a corresponding cost ...
0
votes
0answers
16 views

Convex hull possesses only integer extreme points

I have the following question. Consider given natural numbers $ 1 \le l_m <\ldots < l_1 < L $. Is it possible to prove that the convex hull of $ \left\lbrace a \in \mathbb{Z}^m_{\ge 0} \, \...
2
votes
2answers
569 views

Linear Programming: Breaking Variables Product

Given two sets of binary variables $x_{i...N} \in X$ and $y_{i...M} \in Y$ and another binary variable $\alpha$ how can I linearize the following constraint, i.e break the product of variables? $\...
1
vote
0answers
11 views

Why does the Dantzig cut require the constraint data to be integral?

Given the following integer linear program, (ILP) $\min c'x$ subject to $Ax \ge b, x \in \mathbb{N}_0$ where all elements of $A$ and $b$ are integral, and assuming its linear-program relaxation (...
0
votes
1answer
37 views

System of equations with multiple answers, but only natural numbers (and other constraints)

Okay so basically I want the solution with the smallest sum when you add up the integer variable solutions that give a solution to: $975a + 880b + 790c + 585d + 487e + 440f + 292g + 260h + 530i + ...
3
votes
2answers
65 views

Packing squares in a rectangle

I need to pack $N$ identical squares arranged in array fashion, $R$ rows of $C$ columns, the last row possibly incomplete, in a $W\times H$ rectangle (reals). The squares must be as large as possible. ...
1
vote
1answer
17 views

How to determine lowest integer multiple for any given decimal fraction

In the equation a * b = c, given a, how can I find the lowest integer c provided that: <...
0
votes
2answers
26 views

Formulating an optimisation problem into a mixed-integer problem

I'm not sure if I understand this question and was wondering if anyone could provide any insight to an answer. The only thing I can think of adding is a constraint: "x2 = integer", so I'm clearly ...
0
votes
0answers
20 views

How to linearize a double sum of product of binary variables?

I have a double summation of the form $$ x_{kn}\sum_{k'\in K}\sum_{n'\in N} x_{k'n'} A_{k'n}\leq B_{kn},\quad\forall\; k\in K,n\in N $$ where $x_{kn}$ is a binary variable. How to linearize this ...
0
votes
1answer
26 views

When modeling a multi-objective problem, is there a simple way of choosing to fully minimize one function, then to go on and minimize the second?

I am modelling a problem where I have two objectives. My goal is to fully minimize the first objective function, then choose among the solutions that fully minimized the first objective function to ...
1
vote
1answer
412 views

Linear Integer Programming: consecutive/adjacent variables constraint

Given a set of binary variables $x_{ij} \in X,\ i=0,..,N,\ j=0,..,M$ how do I model an adjacency constraint on $i$'s such that: $\sum_i^N\sum_j^Mx_{ij} = \alpha, \;\text{with }\ 0 < \alpha < N$...
0
votes
0answers
13 views

Solving Binary Linear Programming Problem Using KKT

Execuse me, I know that if I searched a lot I could find the answer, However I have already did my research and I am running out of time. I need the detailed solution of the following linear problem (...
1
vote
2answers
30 views

Binary optimization problem

I am facing the following problem: Let P be a fixed m x n finite matrix and D be a matrix of ones and zeros with the same dimensionality as P plus the following constraints: sum of row entries <=...
4
votes
0answers
157 views

An optimization problem involving Latin Squares

Let $C$ be a given $n \times n$ matrix of real numbers and let $p$ be a given $n$ vector of non-negative numbers such that wlog $\sum_i p_i = 1$ and wlog the $p_i$ are non-increasing. I'll write $C(i,...
1
vote
2answers
38 views

Trying to sell the most batches of animals using linear programming

I'm trying to sell the most batches of animals... Let's say I have 200 dogs, 100 cats, and 100 ferrets. ...
1
vote
1answer
35 views

How to convert a non-linear constraint to a linear constraint for integer programming?

I have non-linear scheduling model and I want to convert it to a linear model. But I have no idea about how can I do it. The nonlinear constraint is: For each $i, i'\in I$ and $j, j' \in J$ and $q, ...
0
votes
1answer
48 views

How to linearize the following constraint on abs terms with coefficients of mixed signs

I am implementing an optimization program on 2 variables with a constraint of the form: 2*|x1| + 3*|x2| <= 2.25 * (|x1| + |x2|) Given that the effective coefficients on the two abs terms are + ...
0
votes
1answer
20 views

Why this scheduling MIP model is not working?

I have an integer programming model for Parallel Machine Scheduling. The parallel machine scheduling problem have $i$ jobs, $j$ process and $k$ number of machines. Each processes has to be done in ...
0
votes
0answers
12 views

Existence of solutions for a scaled integer linear inequality

Assume that I know there exist non-negative integer solutions to a linear system of integer equations (with coefficients from $\{-1,0,1\}$ and non-negative constant terms in my case). Is there any ...
1
vote
1answer
13 views

Mixed Integer linear programming - absolute value of a variable not involved n the objective function

I'm looking to find the absolute value of the expression s-t. I have begun by introducing the following constraints: Where A is the absolute value. Unfortunately, A is not involved in the objective ...
1
vote
1answer
15 views

Tree-width of a quadratic pseudo-Boolean function

A pseudo-Boolean function $f : \mathbb{B}^n \mapsto \mathbb{R}$ is of the following form. $$ f \left(x_1, \ldots, x_n\right) = \sum_{S\subseteq V} c_S \prod_{j \in S} x_j $$ Here $c_S \in \mathbb{R}$,...
2
votes
1answer
79 views

Integer Programming (formulating a problem)

The Record-a-Song Company has contracted with a rising star to record eight songs. The durations of the songs are 8, 3, 5, 5, 9, 6, 7, and 12 minutes, respectively. Record-a-Song uses a two-sided ...
3
votes
1answer
31 views

Transforming a $0$-$1$ knapsack problem into the standard form

I have the following $0$-$1$knapsack problem: $$\begin{align*} &\mathrm{Max} : \quad z= 3x_1 -4x_2+5x_3+7x_4-6x_5+x_6\\ & \mathrm{subject\ to}: -2x_1 +x_2 +10x_3 +3x_4 -5x_5+12x_6 \leq 4 \...
0
votes
0answers
8 views

Correct definition of the co-occurrence graph of a pseudo-Boolean function

In section 4.6 of Pseudo-Boolean Optimization, Boros and Hammer have defined the co-occurrence graph of a pseudo-Boolean function as follows. If a pseudo-Boolean function $f : \mathbb{B}^n \mapsto ...
1
vote
3answers
56 views

Mixed Integer Linear Programming Conditional Constraints

I have a set of variables: $x_1,x_2,x_3,x_4$ $x_1$ is a binary integer variable while the rest are real numbers all between 0 and 1 I want a constraint such that: if $x_2+x_3+x_4$>0 then $x_1=1$ ...
1
vote
0answers
51 views

Develop a model for determining the optimal production schedule in a manufacturing facility

I have to formulate (linearly) the following problem mathematically: What I tried: 1. Variables Let $x_{ijk} = 1$ if, in month k, product i should be made in production line j, where $i=...
0
votes
0answers
38 views

Weights in goal programming

I'm not quite convinced about assigning weights in goal programming. Here is an example formulation problem. What I tried: Let $x_j$ be the number of minutes for ad $j = R, T$ We want to ...
1
vote
0answers
33 views

Model linearly: Determine amount of units for production

A company produces 2 products in a week. Let $x_i$ denote the number of units of product $i$ to produce. Each product requires liters of Chemical X to make. Info is given below: \begin{array}...
0
votes
1answer
15 views

Mixed integer linear programming - making a variable have influence on another variable only when it is equal to zero

Having an integer variable $D \in \{-k,-k+1,...,-1,0,1,...,k-1,k\}$, how do I make it affect another variable only when $D = 0$? Specifically, I have a binary variable $U$ in my model. I want it to ...
0
votes
0answers
25 views

Kinds of logic and constraint programming

I am currently solving combinatorial optimisation problems using integer linear programs (ILP), and I would like to try something different (constraint satisfaction, logic programming, ...). I tried ...
1
vote
3answers
59 views

Integer solutions to $xyz = w^2(x+y+z)$

I'm looking for a way to enumerate all positive integer solutions of the equation $xyz = w^2(x+y+z)$ where $w \le W$ and $1 \le x \le y \le z$. Could anyone provide a hint at how to approach this?
2
votes
0answers
18 views

Does it make sense to compare sets (polygons) with different dimensions?

In the context of integer programming, I am considering 3 different linear models for a given problem. The goal is to determine which formulation is the tightest, that is, the one that gives the least ...
0
votes
1answer
21 views

What is the class of this Integer programming prob.

I have an optimization problem which seems to be non-linear because of the constraints (right?): $max (\sum U_i\times x_i)\\ \sum x_i\times y_i\times r_i\leq R\\ \sum y_i=1\\ \sum x_i=1\\ x_i, y_i\...
0
votes
1answer
23 views

Lower bound for third order polynomial over integers

I have the following polynomial: $P(a,b,c,d) = -2 a + 3 a b + 3 a^2 b + 6 a c + 6 b c + 2 d + 3 a d - 3 a^2 d - 3 b d - 6 a b d - 3 d^2 + 3 b d^2 + d^3 \;,$ where $a$, $b$, $c$, $d$ are integers $\...
0
votes
0answers
8 views

What is the best function to increment a cycling counter over a finite (binary) integer representation?

What is the best function to increment a cycling counter over a finite (binary) integer representation? Edit 1 : i found this https://en.wikipedia.org/wiki/Ring_counter#Johnson_counter Edit 2 : ...
0
votes
0answers
12 views

Pseudo-Boolean functions restricted to integers

The Pseudo-Boolean functions are of the following form. $$ f : \mathbb{B}^n \to \mathbb{R} $$ I would like to know if there is a special sub-category of $$ f : \mathbb{B}^n \to \mathbb{Z} $$ with ...
1
vote
1answer
69 views

Integer programming, system of linear inequalities.

I am woring on a problem and I got these inequalities. $t_{01}+t_{11}+t_{21}\ge 4$ $t_{02}+t_{12}+t_{22}\ge 4$ $t_{10}+t_{11}+t_{12}\ge 4$ $t_{10}+t_{01}+t_{22}\ge 4$ $t_{10}+t_{02}+t_{21}\ge 4$ ...
1
vote
0answers
82 views

What programs or websites solve linear integer or goal programming problems?

I don't think I can use Excel. My solver doesn't work so I can't even use Excel for regular linear programming. Something like this but for integer or goal programming. This seems to allow integer ...
0
votes
0answers
24 views

Linear integer programming

I am trying to find the optimal solution for the following linear integer programming: \begin{eqnarray} &&\underset{x_i, \forall i} {\text{maximize}} ~ \sum_{i=1}^N x_i a_i \\ && \...
0
votes
0answers
27 views

What are the steps to optimize simple Sphere function

I am new to optimization. How can one optimize the simple test function, Sphere function available on https://en.wikipedia.org/wiki/Test_functions_for_optimization?
0
votes
0answers
21 views

Quadratization of $5 x_1 x_2 − 7 x_1 x_2 x_3 x_4 + 2 x_1 x_2 x_3 x_5$ using Rosenberg's algorithm

In section 4.4 of Pseudo-Boolean Optimization by Boros et al., the authors have reproduced Rosenberg's quadratization algorithm as follows. Then they have given an example of implementing the ...
0
votes
2answers
56 views

What method will work for this linear programming problem?

I just started studying linear programming and I have limited resources with which to work. I have to work on a number of exercises but the notes I have do not help much so I have to look online for ...
0
votes
1answer
32 views

Quantifier in Integer Programming/Logic

It is common to write constraints with something like $x_s \leq y \quad \forall s \in X$ In Integer Programming, where x_s and y is a variable. However my tutor said that this not so absolutly ...
0
votes
0answers
30 views

Integer programming with linear constraint

I am trying to find the optimal solution for the following problem \begin{eqnarray} &&\underset{x_i, ~y_i ~\forall i} {\text{maximize}} ~ \sum_{i=1}^N x_i f_i(y_i) \\ && \text{s.t.}...
1
vote
0answers
56 views

Directed Weighted Graph with no cycles - LP

I have directed weighted graph. I have to find a set of edges with minimal sum of their weights that without the set graph becomes acyclic. I can call lp solver multiple times. I'm kind off lost on ...
0
votes
0answers
3 views

How do we accomplish the subtraction of two infinities in a PWL Approximation?

I am trying to implement a piecewise-linear function of an M/M/1 Queueing system in an ILP to approximate the delay values. I have expressed my PWL constraint as follows: $\alpha_{i}+ \beta_{i}u_{n_s} ...
3
votes
0answers
54 views

Candy Crush as an integer programming problem

I'm trying to model the basic version of a match-three game, where the player (has a maximum number of swaps) must swap any two adjacent gems (no diagonals) in an 8x8 grid of gems in order to match ...