Questions on optimization constrained to integer variables.

learn more… | top users | synonyms

1
vote
1answer
74 views

Can this optimization problem be solved?

I am working on an optimization problem but I am not sure if the problem can be formulated as an integer programming problem. Assume the cost minimization problem for a set of subscribers and ...
1
vote
2answers
89 views

Find min/max $\|x\|_{1}$ subject to $Ax = b$, using the simplex method

Let $Ax = b$ be a linear system with $a_{i,j} \in \{0,1\}$ and $b_i \in \{0,1,2,3,4,5,6,7,8\}$. The constraints on $x$ are $x_i \in \{0,1\}$. We suppose that the system admits at least one solution....
2
votes
2answers
580 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
1answer
4k views

Linear programming vs. Integer programming

I was trying to solve a problem where I want to choose which items to choose where each item has a number b_i associated with it and a reward r_i associated with it. I need to choose items that ...
2
votes
0answers
36 views

Showing the integrality property for an Integer Linear Program

I am trying to figure out why solving a relaxed Integer Linear Program (ILP) always give an integral solution. The ILP can be summarized as: $$\min \sum_{t\in T} \sum_{s \in S} c_s k_s^t $$ subject to:...
0
votes
1answer
92 views

How to solve the coupled integer programming problem?

I have the following integer linear programming problem: $$\begin{equation*} \begin{aligned} & \underset{x}{\text{maximize}} && \sum_{k=1}^K\sum_{t=1}^Tx_{kt} \\ & \text{subject to} &...
1
vote
0answers
131 views

Is 0-1 integer programming always NP-hard?

I have the following problem. Maximize $\sum\limits_{m=1}^M\sum\limits_{n=1}^N x_{mn}$ subject to: $\sum\limits_{\substack{m^\prime=1\\ m^\prime \neq m}}^M\sum\limits_{\substack{n^\prime=1\\ n^\...
1
vote
0answers
226 views

Modeling propositional formulas in integer programming

Say I have an binary integer programming problem: \begin{equation*} \begin{aligned} & \underset{\mathbf{x,y}}{\text{minimize}} & & f_0(\mathbf{x,y}) \\ & \text{subject to} & &...
2
votes
1answer
22 views

Model cost for a state change in an integer program

I have a problem involving tool selection I am trying to model right now. (I am fairly new to this). I have a series of manufacturing operations I need to perform for $i \in \{1,\dots,n\}$. Each ...
0
votes
1answer
44 views

Maximum Coin Changes That Does Not Add To a Dollar

What is the maximal amount of money attained from coins of 1, 5, 10, 25 cent denominations that none of its subset amounts to 100 cents? We can find the solution with exhaustive or naive dynamic ...
0
votes
1answer
28 views

Sign of a Linear Expression in Mixed Integer Linear Programming

I have a question about a system in mixed integer programming I am trying to solve using GLPK though the question mathematical and is software agnostic. I have converted the whole problem to linear ...
2
votes
1answer
69 views

Finding the nonnegative integer exponents that minimize a product

I've been trying to solve a problem which seems to be a multiplicative optimization problem: Given a threshold $T > 0$, and a set of integers $b_1, b_2,\dots, b_n > 0$, find integer ...
1
vote
1answer
419 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$...
1
vote
0answers
27 views

Optimizing the product of two integers

How to efficiently solve the following optimization problem? Find $a$ and $b$ which minimize $ c = a * b $ under the constraints $ c \geq C $, $ a \leq A $, $ b \leq B $, where a, b, A, B, C are ...
1
vote
1answer
122 views

Efficient MIP reformulation for binary integer problem

Consider an integer programming model where there is some term $x_ix_j$ where the variables $x_i,x_j \in \{0,1\}$ I want to reformulate this into an efficient mixed-integer programming (MIP) problem. ...
0
votes
1answer
42 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 ...
0
votes
1answer
79 views

Checking whether a solution to MIP is optimal

Consider a binary integer program \begin{align} \min \quad &\sum _{j \in J}f_j x_j +\sum _{i \in I} c_i y_i \notag \\ \mbox{s.t.} \quad &\sum _{j \in N_i} x_j \ge 1-y_i, \quad \forall i\in I \...
8
votes
4answers
561 views

Are there ways to solve equations with multiple variables?

I am not at a high level in math, so I have a simple question a simple Google search cannot answer, and the other Stack Exchange questions does not either. I thought about this question after reading ...
0
votes
1answer
32 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
20 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
110 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
16 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
18 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} \, \...
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
38 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
18 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: <...
1
vote
2answers
29 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
24 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 ...
0
votes
0answers
14 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
31 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
159 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
40 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
40 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
49 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
13 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
15 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
87 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
9 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
59 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
52 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
40 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
34 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
27 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?