Questions on optimization constrained to integer variables.

learn more… | top users | synonyms

0
votes
1answer
10 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
15 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} \, \...
3
votes
2answers
100 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: ...
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
36 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 + ...
1
vote
1answer
16 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: <...
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. ...
0
votes
2answers
25 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
25 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 ...
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 <=...
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
34 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 ...
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
29 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
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}$,...
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 ...
1
vote
1answer
12 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 ...
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 ...
2
votes
0answers
16 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 $\...
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?
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 ...
0
votes
0answers
7 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
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
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
55 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 ...
1
vote
0answers
32 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
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
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
15 views

Integer linear programming - pythagorean theorem approximation

How would one approximate the pythagorean theorem (for cartesian coordinates) in ILP using a reasonable amount of variables and constraints? Basically, given points x1, y1 and x2, y2 $\in \mathbb{R}^...
1
vote
1answer
86 views

Efficient (time complexity) algorithm for Linear Programming problems

I have an inequality of the form: $$\sum_{i=1}^n a_i\cdot x_i \ge a_0$$ where $a_i\gt 0$ for all $i$. Subject to this and $x_i\ge 0$ for all $i$, I have to minimize the expression: $$\sum_{i=1}^n ...
0
votes
0answers
25 views

minimal number of sets of binary vectors

I have a set of binary vectors that I would like to group into a minimal number of sets. A set can be formed when it contains all combinations of elements that vary within that set. Example: for {...
0
votes
1answer
48 views

Minimize the function $f(n,k)=(n-1)-\sqrt{(n-1)^2-4(k-1)(n-k-1)}$ over n,k

For $k\in N, n-2\ge k\ge2$, and $n \in N, n\ge4$ minimize the function $f(n,k)=(n-1)-\sqrt{(n-1)^2-4(k-1)(n-k-1)}$ over n,k EDIT: Attempt to solve First I differentiated it partially w.r.t $k$ and ...
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
1answer
50 views

Is there any algorithm to find all the solutions of the following special linear Diophantine system?

Consider the following system. 1) $a_{11}x_1 + a_{21}x_2 + \cdots + a_{m1}x_m=d_1$ 2) $a_{12}x_1 + a_{22}x_2 + \cdots + a_{m2}x_m=d_2$ $\vdots$ n) $a_{1n}x_1 + a_{2n}x_2 + \cdots + a_{mn}x_m=d_n$ ...
0
votes
1answer
55 views

Packing three increasing integers into one

I have three integers representing positions on a board. Because all pieces are equal, the order does not matter, so it suffices to only consider increasing lists of three integers. However I am ...
0
votes
1answer
51 views

Shortest Path Problem as a Minimum Cost Flow Problem

I have to formulate the well known shortest path problem as a min-cost flow problem, but I don't know how to do it. I need your help and suggestions. Thanks in advance!
0
votes
1answer
25 views

Octave false position

i'm try to write some code in octave based in false position method. So, here it is: And I get the follow error: "parse error near line 40 of file C:\Users\HP...falsa.m syntax error else" So, ...