Questions on optimization constrained to integer variables.

learn more… | top users | synonyms

1
vote
2answers
24 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
37 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
26 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
19 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
66 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
24 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
14 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 ...
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
11 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
22 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
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
11 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
23 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
19 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) \\ && ...
1
vote
0answers
46 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
50 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: ...
0
votes
0answers
37 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
75 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
79 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
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 ...
1
vote
0answers
50 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 ...
0
votes
1answer
46 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
54 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
49 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
24 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
12 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
46 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
68 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
54 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
32 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
78 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 ...