Questions on optimization constrained to integer variables.

learn more… | top users | synonyms

0
votes
0answers
11 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, ...
0
votes
1answer
22 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
9 views

Integer Programming Relaxation

I have the following integer programming problem: $(P_1)$ $max\sum_{j=1}^{5}C_jx_j$ $s.t$ $7/4x_1 - 2/3x_2 + 5/2x_3 - 5/12x_4 + 19/6x_5=7/4$ And I want to show that $(P_2)$ (given below) is ...
0
votes
0answers
10 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
18 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
18 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
28 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
28 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) \\ && ...
0
votes
0answers
22 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} ...
2
votes
0answers
46 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
70 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
14 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 ...
1
vote
1answer
69 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
24 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
47 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 ...
0
votes
1answer
39 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
52 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
45 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
18 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, ...
1
vote
0answers
10 views

Maximizing iterations of finding circular successive differences

From a competition we had in comp sci: Given four integers, $a$, $b$, $c$, and $d$ take repeated absolute differences including $|a-d|$ until you reach all zeros. At each iteration, $a' \gets ...
4
votes
0answers
45 views

Name for “Almost a vector space, but with $\mathbb{N}_0$ instead of a field”

I have a finite set of vectors $V\subset \mathbb{R}^n$ Let us enumerate $V = \{\tilde{v}_1, \tilde{v}_2,...,\tilde{v}_m\}$ I have some space that I want to talk about (I spend a lot of time talking ...
1
vote
1answer
66 views

To show a closed convex set $S \subseteq R^n$ is bounded if and only if $S$ contains no rays.

I want to show that a closed convex set $S \subseteq R^n$ is bounded if and only if $S$ contains no rays. Where $r \in S$ is a ray of $S$ if $x \in S$ implies that $x+\mu r \in S$ for all $\mu \in ...
0
votes
1answer
37 views

How to solve mixed-integer problem?

I don't know how to solve this equation, $$\left\lceil\frac{x-A}{B}\right\rceil C + D x < E, \quad x\in \mathbb{Z}$$ In this equation, only $x$ is unknown and $x$ is integer, but $A,B,C,D,E$ are ...
2
votes
0answers
26 views

Discrete Optimization Problem (VRP)

Consider the following setting : We have two pickup nodes (a) and (b)and two delivery nodes (c) and (d). At each pickup node, there are entities to be picked up and delivered by cars (n cars) to ...
1
vote
1answer
34 views

Are there combinatorial problems that admit closed form solution? [closed]

I was wondering if there's some classes of combinatorial problems (specifically assignment problems) something like maximize: $$ f(\vec{x}) = \sum_{i,j} x_{i}x_{j}2^{i+j}, \;\; x_i \in {0,1} ...
0
votes
2answers
30 views

Writing conditional logic using mathematics forumla

I'm working on an application which has a specific function which receives 2 ints: x and y. If y > x then I would like the function to return y otherwise return x - y. Just a few examples: f(10, ...
1
vote
2answers
53 views

Boolean equation

$$\text{Solve for}\space{x, y}$$ $${a_1, a_2, a_3, a_4, b_1, b_2} \; \text{ - variables}$$ $$\left\{ \begin{aligned} {a_1}\&x \oplus {a_2}\&y &= {b_1} \\ {a_3}\&x \oplus {a_4}\&y ...
2
votes
0answers
30 views

Why does the cutting plane method for integer programming run in exponential time?

I am looking for a proof of the fact that the cutting plane algorithm for integer programming does not run in polynomial time. The algorithm consists in adding constraints to the initial problem in ...
-2
votes
2answers
77 views

Integer programming [closed]

Can anyone help me to find the right solution? How can integer programming be used to ensure that X takes on values 1,3, 5 or any even number less than 100? In practice we have a integer ...
0
votes
1answer
39 views

For any integer $n$ find $x<n$, and $y<n$ to minimize the natural number $z=xy-n$

I need to develop an algorithm for finding the optimal dimensions for setting a set of symbols on a grid (for a typesetting library I'm writing). I need to minimize the number of cells in my grid ...
0
votes
1answer
32 views

Modeling integers in NLP

I was wondering why it is not OK to model binary (integer) variables of an optimization problem, in the following form x(x-1) = 0 What are the consequences for ...
0
votes
0answers
25 views

Approximate ratio with a small fraction so that numerator multiplied by denominator give enough rectangular area?

I would like to layout given number of objects (like plots) into rectangular area (like computer operating system window on screen). I would like to calculate the width and height of the window (in ...
1
vote
1answer
48 views

Set up an integer programming problem so that all variables in the solution are different [closed]

I have a relatively simple minimisation problem. I have to minimise a linear function with many variables (more than 20), and I would like all the solutions to be different and in set $ x \in ...
0
votes
0answers
28 views

Converting a linear-fractional program with an integer constraint to a linear program

Is it possible to convert the following linear-fractional program to a linear program ? $$ \max_x \frac{v\cdot x}{z \cdot x}\\s.t \\x_i \in \{0,1\}\\ \\ \sum_i x_i = k$$ where $v \in R^{d}$, $z \in ...
0
votes
0answers
10 views

Optimize polling frequency between producer and consumer to achieve minimum waiting time

Background: I am trying to optimize what we call AJAX request polling frequency in the domain of web design, and I wanted to check if I could use some help from math guys to explore a better ...
3
votes
1answer
42 views

solve $54 x + 16 y = 2400$ for integer values of x,y

How to get integer values for x and y that satisfy: $$54 x + 16 y = 2400$$ Someone told me that I can do it using Euclid-Wallis algorithm, but I don't understand it so, if there isn't any else ...
1
vote
1answer
50 views

What is the difference between linear and integer programming?

Recently I tried to solve a maximization integer programming problem using linear programming by flooring the max point - but got the wrong answer. I'm wondering if someone can explain mathematically ...
2
votes
1answer
39 views

Solving integer programming problem using the graphical method

I have an integer programming problem I need to solve using the graphical method. Maximize $55x_1 + 500x_2$ such that $$\begin{align} 4x_1 + 5x_2 &\le 2000\\ 2.5x_1 + 7x_2 &\le 1750\\ ...
3
votes
1answer
107 views

Discrete Linear Programming over Finite Fields?

$A$ is an $l\times m$ matrix with integer entries and each column of which contains at least one negative entry. $y$ is a column matrix with integer entries of length $l$. Define the set of sequence ...
0
votes
0answers
12 views

Reference Request For Hermite normal form of non full row rank matrix

Could someone recommend me some references which discuss the problem of the reduction of a matrix which is not full row rank into its Hermite normal form?
0
votes
0answers
35 views

Conditions for a totally unimodular coefficient matrix of a Multi-Commodity-Minimum-Cost-Flow-Problem

I'm considering the following Multi-Commodity-minimum-Cost-Flow-Problem: This leads us to a coefficient matrix $A$ with $N$ donates the incidence matrix of a directed graph and $I$ is the ...
1
vote
0answers
30 views

How to interpret this integer program

I'm having problem understanding the min weight st-cut integer programming in this wiki page: https://en.wikipedia.org/wiki/Max-flow_min-cut_theorem In the min-cut dual part, it has $$d_{ij}-p_i+p_i ...
0
votes
1answer
129 views

Normalized objective function in optimization problem

I have fairly standard linear optimization model with two objectives \begin{align*} \text{max}\, (f_1 &= 4x_1+5 x_2\,,\,f_2 = 1x_1 + 0x_2 ) \\ \text{subject to}& \\ 1x_1 + 1x_2 ...
0
votes
0answers
63 views

KKT conditions (equations) for Generalized Assignment Problem or Binary integer programming problem

I have this formulated Generalized Assignment Problem (GAP) or it can also be considered as Binary integer programming problem. Solving this problem can be achieved through Branch and Bound Technique. ...