Questions tagged [linear-programming]

Optimization with a linear objective function, subject to linear equality and linear inequality constraints.

Filter by
Sorted by
Tagged with
2
votes
1answer
127 views

What is the right term/theory for prediction of Binary Variables based upon their continuous value?

I am working with a linear programming problem in which we have around 3500 binary variables. Usually IBM's Cplex takes around 72 hours to get an objective with a gap of around 15-20% with best ...
1
vote
1answer
129 views

LP Relaxation of Maximum Coverage Problem

So I know from some research I've done that the OPT-IP <= OPT-LP for the maximum coverage problem, however I'm having some difficulty following the explanations I find. Does an example exist where ...
0
votes
0answers
12 views

How to understand the separation phrase for generalized subtour constraints?

Suppose the constraints of our integer programming model consist of two parts: the polynomial-size formulations, that have a size (number of variables and constraints) which is polynomial w.r.t. the ...
0
votes
1answer
111 views

How to write an if then logical constraint given part of the input related to a decision variable?

I am trying to solve an assignment problem-like from a bi-objective persepctive where I have a marketplace of vendors proposing different machines with different types and specs. The goal is to select ...
2
votes
3answers
124 views

Need Help Understanding MST Cutset Formulation

I just started learning about linear programming in my class, and I'm having some trouble understanding the MST Formulation Integer Linear Programming (Cutset Formulation). This is the definition: ...
0
votes
0answers
17 views

LIP - Minimum Spanning Tree Cutset Formulation [duplicate]

I just started learning about linear programming in my class, and I'm having some trouble understanding the MST Formulation Integer Linear Programming (Cutset Formulation). This is the definition: $...
1
vote
0answers
147 views

maximizing absolute value in linear programming

I know that similar questions have been answered several times, and based on the answers, I attempted a solution to my problem. But I simply do not get the right results. The problem is as follows. I ...
2
votes
1answer
26 views

Positioning items to maximize separation

Say we want to place n items on the real line. Let us denote the position of item i by $p_i$. We have interval constraints on the position $p_i$, i.e. we are given $l_i, r_i$ such that $l_i \le p_i \...
1
vote
0answers
17 views

Sparse feasible solution $|x|_0\le k$ for system of linear inequalities $A x \le b$

Suppose the set of linear inequalities $Ax\le b$, in which $A\in\mathbb{R}^{m\times n},x,b\in\mathbb{R}^n$ is given. Is it possible to determine in polynomial time with regard to $m$ and $n$ if there ...
4
votes
1answer
51 views

Is there an algorithm that can find a solution that solves the most number of equations in a linear system of equations?

My apologies if this question makes no sense. I am trying to find an algorithm that can solve a linear system of equations. Unlike most problems like this, this algorithm does not need to find a ...
1
vote
1answer
192 views

A simple way to find the feasible region of a system with simple constraints

I'm coding something... weird, and I'm running into some constraint satisfaction and graph theory problems, which are fields I'm not too experienced in. Here's the problem: I start out with this ...
2
votes
0answers
64 views

Implementing a linear programming feasibility test in 3D

I have a little problem which requires determining if a system of linear inequalities in 3D is infeasible. The constraints (or oriented planes) are added one by one, so there is an opportunity to stop ...
1
vote
2answers
42 views

Better way to formulate these constraints?

I have a binary variable $x_{ijt}^k$ that is $1$ iff job $i$ is assigned to machine $j$ at time $t$ using processor $k$. I would like to express the following constraints: If job $i$ is assigned to ...
0
votes
1answer
82 views

Conditional milp formulation

I have two binaries, $\alpha_{ts,it}$ and $\alpha_{ts,gshp} \in \{0,1\} $, and two reals $T_{it}$ and $T_{ts}$ which have upper and lower bounds. How can I model $\alpha_{ts,it}=1$ if the following ...
1
vote
0answers
59 views

Can somebody suggest what is wrong with these constraint? [closed]

I have written two constraints for Mixed integer linear problem. I am working on the scheduling problem i.e., Scheduling of hybrid appliances. For example, the washing machine is appliance indicated ...
1
vote
2answers
45 views

How to create constraints for Mixed integer linear problem?

i am a beginner to Discrete optimization domain. I am working on the real world problem, i.e., Scheduling of hybrid appliances. I have hybrid appliances which can ...
6
votes
1answer
260 views

How does cycling happen in the simplex method?

I'm reading Schrijver's Theory of Linear and Integer Programming, and I have a problem understanding cycling happens in the simplex method. The simplex is described as below: Solving $\max\{cx\mid x \...
0
votes
0answers
32 views

Does floor and ceiling in LP implies more than $P=NP$?

We know ability to take floor and ceiling in Linear Programming (LP) implies $P=NP$ (just apply floor and ceiling to variable in $(0,2)$ to get binary variable and from this it follows $0/1$ ...
0
votes
1answer
42 views

Can we split a vector into positive and negative parts in LP?

Say you have a vector $v$ with $n$ length $v=\begin{bmatrix}v_1&\dots&v_{n}\end{bmatrix}$ can we write as $v=v_+-v_-$ where $v_+$ agrees with $v$ on non-negative components and is $0$ ...
1
vote
1answer
39 views

Find coverage for plane from half-planes

The document (see pic. below) states that it is possible to find a cover of the plane by a subset of 3 half-planes. It proposes to use linear programming for this. How to formulate such a program? ...
1
vote
0answers
81 views

How to solve this optimization problem with logarithmic objective function?

I have this optimization problem I have no idea how to solve it. Is Lagrange suitable for this problem? Thank you
1
vote
1answer
36 views

Fractional vertex cover number may not be feasible? Very confusing!

For my project, I try to use minimum fractional vertex cover number (MFVC). (Please find below definition details) MFVC can be formulated as optimal solution of a linear program relaxation. However I ...
0
votes
1answer
72 views

How do you proceed if your milp is not solvable

We are currently developing an ilp/milp model to fit the best routes with given resources (people) in a given timeframe and given visits and costs to travel from one visit to another (asymetrical). ...
-1
votes
1answer
68 views

Can we use ILP here?

Is it possible to encode $y=0\implies G=0$ else $G=x$ by Integer Linear Programming where $x,y,G$ are integer variables? The answer mentioned below gets to the point of taking absolute value of ...
-1
votes
1answer
394 views

On if then condition in linear programming?

I have variables $a,b\in\mathbb R$ and if $a>1$ I want $b=1$ or else $b=0$. Can this be encoded by linear programming (no integer variables)? Even $b<0.5$ and $b>0.5$ is ok.
0
votes
0answers
40 views

Linear Programming if-then-else [duplicate]

I have a binary variable $y\ \epsilon\ \{0,1\} $ and a real $x$ which has the following boundaries $-100\leq\ x \leq\ 100$. How can I reformulate the following statement: $$ y = \begin{cases} 0 & ...
3
votes
2answers
283 views

How to check if a specific ILP problem can be solved in polynomial time or not?

How can we know that a specific ILP problem is solvable in polynomial time or not given the constraints?
2
votes
1answer
987 views

Why is integer programming more difficult than (real) linear programming? [duplicate]

Why is integer programming (IP) more difficult than (real) linear programming (LP)? I searched a lot on the web, but I didn't find an answer.
1
vote
0answers
501 views

Restriction for greater than constraint in linear programming

I have a model that considers real values and that uses a binary variable $x$. In this model, the following conditions should apply: \begin{equation} x= \begin{cases} 0, & \text{if}\...
2
votes
1answer
296 views

Bipartite Perfect Matching “Assignment Problem” - finding an assignment of a particular weight

The assignment problem is to find the minimum weight perfect matching in a weighted bipartite graph. This problem can be solved using the Hungarian algorithm in polynomial time. It is also possible to ...
6
votes
1answer
435 views

How to find the supremum over all the “good” (interior) polytopes for a given set of 3D points?

Let $S \subset \mathbf{R}^3$ be a set of points in 3D and let $O=(x_0,y_0,z_0)$ be the origin/point of reference. We consider a convex polytope $P$ good / interior if: $P$ is wholly contained ...
0
votes
0answers
59 views

How to model an ''affinity constraint'' in assignment problem

Working on an optimization problem formulated using the well known assignment problem. My decision variable is defined as follows : $$\alpha _{x}^{r,u} = 1\begin{cases} & \text{ 1 if } \mathbf{...
0
votes
0answers
23 views

Problem with formulating LP problem using binary variables

I have a problem with a task shown below. I have I am supposed to use big M method, but I don't know how to estimate/compute the minimal value of it and how to implement it into the equations. Any ...
2
votes
1answer
121 views

Converting nested absolute value into linear programming

I am having trouble writing the following optimization problem as a linear program (LP) $$\min_{x \in \mathbb R^2} \big| | x_{1} - a_{1} | - | x_{2} - a_{2} | \big|$$ where $a \in \mathbb Z^2$ is ...
1
vote
1answer
34 views

Example of $c^Tx' = c^Tx$ where x is the optimal solution for the linear relaxation (LP) of x' (ILP)

I am looking for an example where the optimal solution for the LP problem is equal to the optimal solution of the ILP problem, but the solutions are different. All I managed to think of was the ...
0
votes
1answer
13 views

Relating indexes for parameters and variables

I am trying to solve a referee assignment problem, but I simply can't think of a way to relate my variable to one of the parameters, and I hope that someone in here can help. I have the following ...
1
vote
0answers
157 views

LP realaxation for multicut problem with polynomial number of constraints

The integer linear programming formulation for the multicut problem for the given graph $G = (V,E)$ and distinguished source-sink pairs of vertices $(s_1,t_1),...,(s_k,t_k)$ is: \begin{alignat}{3} \...
1
vote
1answer
84 views

Can LP for matroid polytopes be solved using the greedy algorithm?

For general linear programming (LP), i.e. optimization of a linear objective over a general polyhedron, to the best of my knowledge/recollection one can use the simplex algorithm (or hypothetically, ...
2
votes
1answer
459 views

Questions about Amdahl's law?

Doing exam papers now and I came across two questions which I cannot get my head around sadly. Both are regarding Amdahl's law and Parallel Computing but they seem rather simple and frustratingly ...
1
vote
0answers
34 views

Time complexity bounds for the approximation of optimal values of bounded linear programs

Assume we are given a LP maximization problem defined by a linear functional $c^Tx$ and a non-empty feasible region $\{x:Ax\leq b\}$ that is known to be bounded by a hypercube of side $R>0$, say $[...
0
votes
1answer
257 views

Converting between (standard) primal to dual forms (LP)

I'm working on a HW assignment as follows: Given the primal canonical problem: $$min \langle c,x \rangle \text{ s.t. } Ax \geq b, x \geq 0$$ and the canonical dual problem: $$ max \langle b,y \rangle ...
2
votes
1answer
54 views

Maximize the number of edges in subgraph

We are given a graph $G=(V,E)$ and we want an algorithm to find a set of vertices $U$ to maximize the following quantity : $\frac{|E(U)|}{|U|}$ where $E(U)$ denotes the number of edges in the subgraph ...
0
votes
1answer
197 views

LP formulation and integer solution existance

I’m trying to prove that the following problem has an integer optimal solution. This will hold if the corresponding linear program would have totally unimodular constraint matrix. We have $m$ pieces ...
0
votes
1answer
40 views

Why is the target function minimized at (0,0) if I can get to a negative number?

I just started learning LP and I saw this Q in my textbook: $$ min : -x -y \\ S.T. : x + 2y \le 3, 2x +y \le 3, x \ge 0, y \ge 0 $$ It is easy to see that the polygon created from these constraints ...
1
vote
1answer
356 views

Finding integrality gap for maximum weight independent set

One of the exercises I was given was to formulate Integer Linear Program (ILP) and relaxed version of it (LP) to solve the maximum weight independent set, and I need to find an integrality gap of my ...
0
votes
1answer
60 views

Objective function and constraint satisfaction over a set of multi-attributes elements

I'm looking for an approach to solve a problem consisting of maximizing an objective function over a set of discrete elements, while respecting a set of constraints. To illustrate my point, I'll try ...
1
vote
1answer
46 views

Simplex Algorithm: Why must the optimal value of the LP lie on the face or vertex of a polyhedron?

The feasible region of a Linear Program (LP) is $\{x \in {\bf R}^n: Ax \le b, x\ge 0 \}$. This is an intersection of halfspaces, a polyhedron. If the LP is bounded and feasible, its optimal value will ...
-1
votes
1answer
2k views

Expressing conditional in linear program [duplicate]

I have two variables $A$ and $B$, with $A$ being binary and $B$ is a real number where $B \ge 0$. My conditions are: if B > 0 A = 1 else A = 0 ...
0
votes
0answers
47 views

How to monitor and alter the value of decision variables using if then else

Assuming I have two 0-1 decision variables X[a,b] and Y[i,j,e,d] where : X[a,b] = 1 if a is in b 0 otherwise Y[i,j,e,d] = 1 if (i,j) is matched with (e,d) 0 otherwise. I need to ensure that if ...
2
votes
3answers
433 views

Max flow with priorities

I'm studying a simple max flow problem: Each type of object $a_1, a_2...$ can be stored in some of several stores $b_1,b_2...$. This is described by this graph: There are $|a_i|$ objects of the type ...